最长相同子字符串(LCS)
动态规划
class Solution {
public String longestCommonString(String s1, String s1) {
int len1 = s1.length();
int len2 = s2.length();
int left = 0;
int max_len = 0;
// 动态规划
int dp[][] = new int[len1+1][len2+1];
// dp[i][j] 表示在s1[i]==s2[j] 时，s1[1~i]和s2[1~j]的LCS
for(int i = 0; i<= len1; i++) {
for(int j = 0; j<=len2; j++) {
if(i == 0 || j == 0) {
dp[i][j] = 0;
} else if(s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
max_len = Math.max(max_len, dp[i][j]);
if(max_len == dp[i][j]) {
left = i-max_len;
}
} else {
dp[i][j] = 0;
}
}
}
return s1.substring(left, left+max_len);
}
}