题意:就是一个最长公共子序列。并打印其路径。
分析:最长公共子序列还不难,注意是打印它的一条路径。我们知道是用二维数组dp来保存它的匹配数。一旦有匹配的它就修改后面的值,保证了
如何一个状态当前的dp数据中是最大的值。看一张经典的图:
显示了路径的回溯。帮助我们能找到匹配的的过程。
为了记录它转移的方向。我们需要用辅助数组map来记录它是有那个状态转移而来的。可以用递归来实现。
代码如下:
- #include<cstdio>
- #include<cstring>
- //using namespace std;
- int dp[105][105],map[105][105];
- char s[100][35],t[100][35];
- void LCS(int a,int b)
- {
- for(int i=1;i<=a;i++)
- for(int j=1;j<=b;j++)
- if(strcmp(s[i-1],t[j-1])==0)
- {
- dp[i][j]=dp[i-1][j-1]+1;
- map[i][j]=1;
- }
- else{
- if(dp[i-1][j]>=dp[i][j-1])
- {
- map[i][j]=2;
- dp[i][j]=dp[i-1][j];
- }
- else
- {
- map[i][j]=3;
- dp[i][j]=dp[i][j-1];
- }
- }
- }
- void path(int a,int b) //打印LCS路径
- {
- if(a==0||b==0) return;
- if(map[a][b]==1){
- path(a-1,b-1);
- printf("%s ",s[a-1]);
- }
- else if(map[a][b]==2)
- path(a-1,b);
- else
- path(a,b-1);
- }
- int main()
- {
- int i,j,len1,len2;
- while(scanf("%s",s[0])!=EOF)
- {
- //memset(dp,sizeof(dp));
- for(len1=1;;len1++)
- {
- scanf("%s",s[len1]);
- if(strcmp(s[len1],"#")==0) break;
- }
- for(len2=0;;len2++)
- {
- scanf("%s",t[len2]);
- if(strcmp(t[len2],"#")==0) break;
- }
- LCS(len1,len2);
- path(len1,len2);
- printf("\n");
- }
- return 0;
- }