最长公共子序列、上升子序列、最长上升子序列、最长公共子串

最长公共子序列

其实有很多方法可以过，因为在弄DP所以就只写了动态规划的方法：

动态规划方法

1、序列str1和序列str2

·长度分别为m和n；

·创建1个二维数组L[m.n]；

·初始化L数组内容为0

·m和n分别从0开始，m++，n++循环：

- 如果str1[m] == str2[n]，则L[m,n] = L[m - 1, n -1] + 1；

- 如果str1[m] != str2[n]，则L[m,n] = max{L[m,n - 1]，L[m - 1, n]}

·最后从L[m,n]中的数字一定是最大的，且这个数字就是最长公共子序列的长度

·从数组L中找出一个最长的公共子序列

2、从数组L中查找一个最长的公共子序列

i和j分别从m，n开始，递减循环直到i = 0，j = 0。其中，m和n分别为两个串的长度。

·如果str1[i] == str2[j]，则将str[i]字符插入到子序列内，i--，j--；

·如果str1[i] != str[j]，则比较L[i,j-1]与L[i-1,j]，L[i,j-1]大，则j--，否则i--；（如果相等，则任选一个）

根据上图，我们可以得到其中公共子序列：B C B A 和 B D A B。

 1 # include <map>
 2 # include <queue>
 3 # include <stack>
 4 # include <math.h>
 5 # include <stdio.h>
 6 # include <string.h>
 7 # include <iostream>
 8 # include <algorithm>
 9 # define N 510
10 using namespace std;
11 
12 char s1[N], s2[N];
13 int dp[N][N];
14 
15 int max(int x, int y)
16 {
17     if(x > y)
18         return x;
19     else
20         return y;
21 }
22 
23 int main(void)
24 {
25     while(gets(s1))
26     {
27         gets(s2);
28         int len1 = strlen(s1);
29         int len2 = strlen(s2);
30         for(int i = 0; i <= len1; i++)
31             for(int j = 0; j <= len2; j++)
32                 dp[i][j] = 0;
33         for(int i = 1; i <= len1; i++)
34         {
35             for(int j = 1; j <= len2; j++)
36             {
37                 if(s1[i-1] == s2[j-1])
38                     dp[i][j] = dp[i-1][j-1]+1;
39                 else
40                 {
41                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
42                 }
43             }
44         }
45         printf("%d
", dp[len1][len2]);
46     }
47 
48     return 0;
49 }

View Code

很好的一篇介绍LCS的文章http://blog.csdn.net/v_july_v/article/details/6695482

最长上升子序列

 1 # include <map>
 2 # include <queue>
 3 # include <stack>
 4 # include <math.h>
 5 # include <stdio.h>
 6 # include <string.h>
 7 # include <iostream>
 8 # include <algorithm>
 9 # define N 1010
10 using namespace std;
11 
12 int a[N], dp[N];
13 
14 int main(void)
15 {
16     int n, m, i, j;
17     scanf("%d", &n);
18     for(i = 1; i <= n; i++)
19         scanf("%d", &a[i]);
20     dp[1] = 1;
21     for(i = 2; i <= n; i++)
22     {
23         m = 0;
24         for(j = 1; j < i; j++)
25         {
26             if(a[i] > a[j] && m < dp[j])
27                 m = dp[j];
28         }
29         dp[i] = m+1;
30     }
31     int nMax = -1;
32     for(i = 1; i <= n; i++)
33     {
34         if(nMax < dp[i])
35             nMax = dp[i];
36     }
37     printf("%d
", nMax);
38 
39     return 0;
40 }

View Code

上升子序列（最长上升子序列改版求和）

 1 # include <map>
 2 # include <queue>
 3 # include <stack>
 4 # include <math.h>
 5 # include <stdio.h>
 6 # include <string.h>
 7 # include <iostream>
 8 # include <algorithm>
 9 # define N 1010
10 using namespace std;
11 
12 int a[10000], dp[10000];
13 int main(void)
14 {
15     int n, max, i, j;
16     while (~scanf("%d",&n))
17     {
18         for (i = 0; i < n; i++)
19             scanf("%d", &a[i]);
20         dp[0] = a[0];
21         for (i = 0; i < n; i++)
22         {
23             max = 0;
24             for (j = 0; j < i; j++)
25             {
26                 if (a[i] > a[j])
27                 {
28                     if (max < dp[j])
29                         max = dp[j];
30                 }
31             }
32             dp[i] = a[i] + max;
33         }
34         int t = 0;
35         for (i = 0; i < n; i++)
36         {
37             if (t < dp[i])
38                 t = dp[i];
39         }
40         printf("%d
", t);
41     }
42 
43     return 0;
44 }

View Code

最长公共子串

 1 # include <stdio.h>
 2 # include <string.h>
 3 
 4 int dp[30010], n, t;
 5 char c[101], len[101], a[101][101];     /* 这里存储着状态数列, 长度 */
 6 
 7 int get(int i, int k)                    /* 得到状态 */
 8 {
 9     if (i > n)
10         return 0;
11     return get(i+1, k*len[i]) + k * c[i];
12 }
13 
14 int LCS()
15 {
16     int p, i, j;
17     p = get(0, 1);
18     if (!dp[p])
19     {
20         for(i = 1; i <= n-1; i++)
21             if (a[i][c[i]] != a[i+1][c[i+1]])
22                 break;
23         if (i > n - 1)
24         {
25             for(i=1; i<=n; ++i)
26             {
27                 if (c[i])
28                     c[i]--;
29                 else
30                     break;
31             }
32             if (i > n)
33             {
34                 j = LCS() + 1;
35                 if (j >= dp[p])
36                     dp[p] = j + 1;
37             }
38             else
39             {
40                 dp[p] = 2;
41             }
42             while((--i)>0)
43             {
44                 c[i]++;
45             }
46         }
47         else
48         {
49             for(i = 1; i <= n; i++)
50             {
51                 if(c[i])
52                 {
53                     c[i]--;                /* 遍历前一个状态 */
54                     j = LCS();
55                     if (j >= dp[p])
56                         dp[p] = j + 1;
57                     c[i]++;
58                 }
59             }
60             if (!dp[p])
61                 dp[p] = 1;
62         }
63     }
64     return dp[p] - 1;
65 }
66 
67 int main(void)
68 {
69     int i;
70     scanf("%d", &t);
71     while(t--)
72     {
73         scanf("%d", &n);
74         memset(dp, 0, 30000*sizeof(dp[0]));
75         len[0] = 1;
76         for(i = 1; i <= n; i++)
77         {
78             scanf("%s", a[i]);
79             len[i] = strlen(a[i]);
80             c[i] = len[i] - 1;
81         }
82         printf("%d
", LCS());           /* 进行倒推 */
83     }
84 }

View Code

公共字串理解的还不是很深刻留代码= =、