首先区别最长公共子串和最长公共子序列
最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。
最长公共子序列:
http://acm.hdu.edu.cn/showproblem.php?pid=1159
#include <iostream> #include <algorithm> #include <string> #include <string.h> using namespace std; string s1, s2; ][]; int main(){ while (cin >> s1 >> s2){ memset(dp,,sizeof(dp)); ; i <= s1.length(); i++){ ; j <= s2.length(); j++){ ] == s2[j - ]) dp[i][j] = dp[i - ][j - ] + ; else dp[i][j] = max(dp[i - ][j], dp[i][j - ]); } } cout << dp[s1.length()][s2.length()] << endl; } ; }
最长公共子串:
两个算法特别像,只不过子序列 碰到相等字符修改的值,可以往后“遗传”
#include <iostream> #include <algorithm> #include <string> #include <string.h> using namespace std; string s1, s2; ][]; int main(){ while (cin >> s1 >> s2){ memset(dp,,sizeof(dp)); ; ; i <= s1.length(); i++){ ; j <= s2.length(); j++){ ] == s2[j - ]) dp[i][j] = dp[i - ][j - ] + ; if (dp[i][j] > max)max = dp[i][j]; } } cout << max << endl; } ; }