| a | b | c | f | b | c | |
| a | 1 | 1 | 1 | 1 | 1 | 1 |
| b | 1 | 2 | 2 | 2 | 2 | 2 |
| f | 1 | 2 | 2 | 3 | 3 | 3 |
| c | 1 | 2 | 3 | 3 | 3 | 4 |
| a | 1 | 2 | 3 | 3 | 3 | 4 |
| b | 1 | 2 | 3 | 3 | 4 | 4 |
测试数据：
abfcab
abcfbc
输出结果：
4
a b f c
0 2 2 2 2 2
1 0 2 2 0 2
1 1 1 0 2 2
1 1 0 1 1 0
0 1 1 1 1 1
1 0 1 1 0 1
1 1 1 1 1 1
1 2 2 2 2 2
1 2 2 3 3 3
1 2 3 3 3 4
1 2 3 3 3 4
1 2 3 3 4 4
请按任意键继续. . .
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int dp[MAXN][MAXN];
int flag[MAXN][MAXN];
char dest[MAXN];
char str[MAXN];
int LCS(int x, int y)
{
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
if(dest[i-1] == str[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
flag[i][j] = 0;
}
else if(dp[i-1][j] >= dp[i][j-1])
{
dp[i][j] = dp[i-1][j];
flag[i][j] = 1;
}
else
{
dp[i][j] = dp[i][j-1];
flag[i][j] = 2;
}
}
}
return dp[x][y];
}
void ShowLCS(int x, int y)
{
if(x == 0 || y == 0) return;
if(flag[x][y] == 0)
{
ShowLCS(x-1,y-1);
cout<<dest[x-1]<<" ";//第一行第一列为空数据区
}
else if(flag[x][y] == 1)
{
ShowLCS(x-1,y);
}
else
{
ShowLCS(x,y-1);
}
}
int main()
{
freopen("in.txt","r",stdin);
cin>>dest>>str;
int dest_len = strlen(dest);
int str_len = strlen(str);
cout<<LCS(dest_len,str_len)<<endl;
ShowLCS(dest_len,str_len);
cout<<"\n\n";
for(int i=0;i<=dest_len;i++)
{
for(int j=0;j<=str_len;j++)
{
cout<<flag[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
for(int i=0;i<=dest_len;i++)
{
for(int j=0;j<=str_len;j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}