【模板】最长相同子序列

 1 /*
 2 LCS
 3 
 4 BDCABA
 5 ABCBDAB
 6 
 7 dp[1][2] = 1
 8 dp[1][1] = 0
 9 dp[2][1] = 0
10 
11 //子串：连续
12 //子序列：可以不连续 
13 // LCS
14 
15 dp[i][j]//第一个字符串在第i个字符前且第二个串在第j个字符前可构成的最长子序列的长度 
16 
17 dp[i][j] =             0                          i=0 || j=0
18                 dp[i-1][j-1]+1             str1[i]==str2[j]
19             max(dp[i-1][j],dp[i][j-1])     str1[i]!=str2[j]
20 */
21 #include<cstdio>
22 #include<cstring>
23 #include<stack>
24 #include<algorithm>
25 using namespace std;
26 int main()
27 {
28     char str1[20];
29     char str2[20];
30     scanf ("%s %s",str1+1,str2+1);
31     str1[0] = str2[0] = '0';
32     int l1 = strlen(str1)-1;
33     int l2 = strlen(str2)-1;
34     int dp[20][20] = {0};//0                          i=0 || j=0
35     
36     for (int i = 1 ; i <= l1 ; i++)
37     {
38         for (int j = 1 ; j <= l2 ; j++)
39         {
40             if (str1[i] == str2[j])//dp[i-1][j-1]+1             str1[i]==str2[j]
41                 dp[i][j] = dp[i-1][j-1] + 1;
42             else
43                 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//max(dp[i-1][j],dp[i][j-1])     str1[i]!=str2[j]
44         }
45     }
46     
47     //回溯求LCS 
48     int pos1 = l1;
49     int pos2 = l2;
50     stack<char> S;
51     while (pos1 > 0 && pos2 > 0)
52     {
53         if (str1[pos1] == str2[pos2])
54         {
55             S.push(str1[pos1]);
56             pos1--;
57             pos2--;
58         }
59         else if (dp[pos1-1][pos2] > dp[pos1][pos2-1])
60             pos1--;
61         else
62             pos2--;
63     }
64     while (!S.empty())
65     {
66         printf ("%c%c",S.top(),(S.size() == 1) ? '
' : ' ');
67         S.pop();
68     }
69     printf ("%d
",dp[l1][l2]);
70     return 0;
71 }