本网站正在建设升级中,网页游戏开发技术,怎么在线上推广自己的产品,网站不备案会怎...公共子串公共子串公共子串
Description
设有A、B两个字符串#xff0c;找出A、B共同子串#xff0c;每个字符串无相同字符#xff0c;可以不连续#xff0c;但顺序不能颠倒。
Input
第一行字符串A
第二行字符串#xff22;
Output
最长公共子串的长度.
Sample Inp…公共子串公共子串公共子串
Description
设有A、B两个字符串找出A、B共同子串每个字符串无相同字符可以不连续但顺序不能颠倒。
Input
第一行字符串A
第二行字符串
Output
最长公共子串的长度.
Sample Input
abcfbc
abfcab
Sample Output
4
解题方法
用i和j来枚举A和B的当前字符动态转移方程如下
f[i][j]{max(f[i][j],f[i−1][j−1]1)a[i]b[j]max(f[i−1][j],f[i][j−1])a[i]≠b[j]f[i][j]\left\{\begin{matrix} max(f[i][j],f[i-1][j-1]1) amp; a[i]b[j]\\ max(f[i-1][j],f[i][j-1]) amp; a[i]\neq b[j] \end{matrix}\right.f[i][j]{max(f[i][j],f[i−1][j−1]1)max(f[i−1][j],f[i][j−1])a[i]b[j]a[i]̸b[j]
#includecstdio
#includeiostream
#includecstring
#includestring
using namespace std;
int n,m,f[255][255];
string a,b;
int main()
{getline(cin,a);getline(cin,b);na.size();mb.size();a a;b b;for (int i1;in;i)for (int j1;jm;j){f[i][j]max(f[i-1][j],f[i][j-1]);//动态转移方程if (a[i]b[j]) f[i][j]max(f[i][j],f[i-1][j-1]1);//判断当前字符是否相同}printf(%d,f[n][m]);
}
