状态表示：f [ i ] [ j ] 表示a串的第i个， b串的第j个之前的最大公共子串长度
所以
状态转移有三种情况，取i不取j，取j不取i，取i又取j
在i，j指向的字符相同的情况下，直接转移到第三种状态就行
如果不相同 就要在前两种状态里选择长度更长的一种
状态计算：f [ i ] [ j ] = max ( f [ i - 1 ] [ j ] , f [ i ] [ j - 1 ] ) (a [ i ] ! = b [ j ])
f [ i ] [ j ] = max ( f [ i ] [ j ] , f [ i - 1 ] [ j - 1 ] + 1 )
#include
using namespace std;stack stk;char a[3050],b[3050];
int f[3050][3050];
char logo[3050][3050];//用来标记答案字符串int main()
{scanf("%s%s",a+1,b+1);for(int i=1;i<=strlen(a+1);i++){for(int j=1;j<=strlen(b+1);j++){if(a[i]!=b[j]){f[i][j]=max(f[i-1][j],f[i][j-1]);}else f[i][j]=max(f[i][j],f[i-1][j-1]+1),logo[i][j]='=';}//相同字符会被打上标记}int x=1,y=1;for(int i=1;i<=strlen(a+1);i++){for(int j=1;j<=strlen(b+1);j++)if(f[x][y]0;i--){for(int j=y;j>0;j--){if(logo[i][j]=='='&&f[i][j]==temp)temp--,stk.push(a[i]),i--;}目标字符串不仅要带标记，每个字符所对应的长度还应递减}while(!stk.empty())cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
