本文主要是介绍hiho一下 第六十周 题目1 : String Matching Content Length dp 最长公共子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目1 : String Matching Content Length
-
abcdefghijklmn ababceghjklmn
样例输出 -
8
描述
We define the matching contents in the strings of strA and strB as common substrings of the two strings. There are two additional restrictions on the common substrings.
The first restriction here is that every common substring's length should not be less than 3. For example:
strA: abcdefghijklmn
strB: ababceghjklmn
The matching contents in strA and strB are substrings ("abc", "jklmn"). Note that though "e" and "gh" are common substrings of strA and strB, they are not matching content because their lengths are less than 3.
The second restriction is that the start indexes of all common substrings should be monotone increasing. For example:
strA: aaabbbbccc
strB: aaacccbbbb
The matching contents in strA and strB are substrings ("aaa", "bbbb"). Note that though "ccc" is common substring of strA and strB and has length not less than 3, the start indexes of ("aaa", "bbbb", "ccc") in strB are (0, 6, 3), which is not monotone increasing.
输入
Two lines. The first line is strA and the second line is strB. Both strA and strB are of length less than 2100.
输出
The maximum length of matching contents (the sum of the lengths of the common substrings).
类似于经典的最长公共子序列的做法。
dp[i][j][3]第一个串s1前i位 第二个串s2前j位，最后一个子串长度为0 1 2 3(>=3)的最长公共子序列。
状态转移
1,dp[i][j][0]转移到dp[i-1][j][0],dp[i-1][j][3] dp[i][j-1][0] dp[i][j-1][3];也就是第s1[i] 与s2[j]不匹配，直接转移到前一位就可以了。
2.s1[i] == s2[j]则，dp[i][j][k]可以转移到dp[i][j][k-1];也就是同是加一位。
初始化的时候，要注意，dp[0][i],dp[i][0]都为0;
由于有n * n个状态，状态转移为o(1)所有总的复杂度为O(n *n);
其次，给些测试数据
abcdefghijklmn
ababceghjklmn
aaabbbbccc
aaacccbbbb
aaa
aaa
ab
ab
aaaab
baaaa
abcba
bcbaa
babad
babacabad
abcdef
abcxcdef
#define N 2205
#define M 100005
#define maxn 2000005
#define MOD 1000000000000000007
int n,m,dp[N][N][4];
char s1[N],s2[N];
int main()
{//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);while(SS(s1)!=EOF){SS(s2);n = strlen(s1);m = strlen(s2);FI(n) FJ(m) For(k,0,4) dp[i][j][k] = -1;FI(n+1)dp[0][i][0] = dp[i][0][0] =0;For(i,1,n+1){For(j,1,m+1){dp[i][j][0] = max(dp[i][j][0],dp[i][j-1][0]);dp[i][j][0] = max(dp[i][j][0],dp[i-1][j][0]);dp[i][j][0] = max(dp[i][j][0],dp[i][j-1][3]);dp[i][j][0] = max(dp[i][j][0],dp[i-1][j][3]);if(s1[i-1] == s2[j-1]){For(k,1,4)if(dp[i-1][j-1][k-1] >= 0)dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-1] + 1);if(dp[i-1][j-1][3] >= 0)dp[i][j][3] = max(dp[i][j][3],dp[i-1][j-1][3] + 1);}}}printf("%d\n",max(0,max(dp[n][m][0],dp[n][m][3])));}//fclose(stdin);//fclose(stdout);return 0;
}
这篇关于hiho一下 第六十周 题目1 : String Matching Content Length dp 最长公共子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
