模板最长公共子序列

【模板】最长公共子序列
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 char s1[1000],s2[1000];
 7 int len1,len2,dp[1000][1000],mark[1000][1000];//如果数据太大，dp数组可以考虑滚动数组
 8 
 9 void LCS()
10 {
11     int i,j;
12     memset(dp,0,sizeof(dp));
13     for(i = 0;i<=len1;i++)
14     mark[i][0] = 1;
15     for(i = 0;i<=len2;i++)
16     mark[0][i] = -1;
17     for(i = 1; i<=len1; i++)
18     {
19         for(j = 1; j<=len2; j++)
20         {
21             if(s1[i-1]==s2[j-1])
22             {
23                 dp[i][j] = dp[i-1][j-1]+1;
24                 mark[i][j] = 0;
25             }
26             else if(dp[i-1][j]>=dp[i][j-1])
27             {
28                 dp[i][j] = dp[i-1][j];
29                 mark[i][j] = 1;
30             }
31             else
32             {
33                 dp[i][j] = dp[i][j-1];
34                 mark[i][j] = -1;
35             }
36         }
37     }
38 }
39 
40 void PrintLCS(int i,int j)
41 {
42     if(!i && !j)
43     return ;
44     if(mark[i][j]==0)//公共的
45     {
46         PrintLCS(i-1,j-1);
47         printf("%c",s1[i-1]);
48     }
49     else if(mark[i][j]==1)
50     {
51         PrintLCS(i-1,j);
52         printf("%c",s1[i-1]);
53     }
54     else
55     {
56         PrintLCS(i,j-1);
57         printf("%c",s2[j-1]);
58     }
59 }
模板 最长公共子序列

模板最长公共子序列
