lintcode 79. 最長共通サブストリング動的計画
7155 ワード
2つの文字列を指定し、最長の共通サブ列を見つけ、その長さを返します.
1:
: "ABCD" and "CBCE"
: 2
:
"BC"
2:
: "ABCD" and "EACB"
: 1
:
'A' 'C' 'B'
O(n x m) time and memory.
， 。
class Solution {
public:
/**
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
// write your code here
int n1=A.size();
int n2=B.size();
if(n1==0||n2==0) return 0;
vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
int max=-1;
for (int i = 1; i <= n1; i++) {
/* code */
for (int j = 1; j <= n2; j++) {
/* code */
if(A[i-1]==B[j-1])
dp[i][j]=dp[i-1][j-1]+1;
max=max>dp[i][j]?max:dp[i][j];
}
}
return max;
}
};