动态规划——最长公共子串

引入：

最长公共子序列常用于解决字符串的相似度问题。

最长公共子序列（Longest Common Subsequence，LCS）与最长公共字串（Longest Common Substring）：子串是串的一个连续的部分，子序列则是从不改变序列顺序，而从序列中去掉任意多个元素而获得的新的序列；也就是说，子串中字符的位置一定是连续的，而子序列不一定连续。

a not the 之一(得到的未必就是唯一的那个最长公共子串，只有长度是唯一的)

——其余字符串问题，待续

解决方案：

1、穷举法（Bruke force alg ）

a[m] and b[n]

check every sequence of a ，to see if it is a sequence of b .

analysis:

check = O(N)

2^m subsequence of a

so O(n*2^m)=slow

不可取：一个长度为N的字符串，其子序列有2^N个，指数级的复杂度。

2、递归法

对于字符串a[ ]和 b[ ]，当a与b位置上的字符相同时，则直接求解下一个位置，当不同时取两种情况下较大的数值。

 1 #include<stdio.h>
 2 
 3 #include<string.h>
 4 
 5 char a[30],b[30];
 6 
 7 int lena,lenb;
 8 
 9 int LCS(int,int);　　///两个参数分别表示数组a的下标和数组b的下标
10 
11 int main()
12 
13 {
14 
15     strcpy(a,"ABCBDAB");
16 
17     strcpy(b,"BDCABA");
18 
19     lena=strlen(a);
20 
21     lenb=strlen(b);
22 
23     printf("%d
",LCS(0,0));
24 
25     return 0;
26 
27 }
28 
29 int LCS(int i,int j)
30 
31 {
32 
33     if(i>=lena || j>=lenb)
34 
35         return 0;
36 
37     if(a[i]==b[j])
38 
39         return 1+LCS(i+1,j+1);
40 
41     else
42 
43         return LCS(i+1,j)>LCS(i,j+1)? LCS(i+1,j):LCS(i,j+1);
44 
45 }

代码实现

优点：容易理解，编程简单，

缺点：效率低下，有大量重复执行的递归调用，且只能求出最大公共子序列的长度，不能得到具体的公共子序列。

3、动态规划

改进：采用二维数组来标记中间结果，避免重复的计算以便提高效率。

对于字符串a[]和 b[]，num[i][j]记录序列a[ i]和 b[j ]的最长公共子序列的长度，其中，a[ i]即{a1,a2,....,ai}和 b[j ]即{b1,b2,....,bj}

b[i][j]来记录c[i][j]的值是由哪一个子问题的解得到的。

  1 #include<stdio.h>
  2 
  3 #include<string.h>
  4 
  5  
  6 
  7 char a[500],b[500];
  8 
  9 char num[501][501]; ///记录中间结果的数组
 10 
 11 char flag[501][501];    ///标记数组，用于标识下标的走向，构造出公共子序列
 12 
 13 void LCS(); ///动态规划求解
 14 
 15 void getLCS();    ///采用倒推方式求最长公共子序列
 16 
 17  
 18 
 19 int main()
 20 
 21 {
 22 
 23     int i;
 24 
 25     strcpy(a,"ABCBDAB");
 26 
 27     strcpy(b,"BDCABA");
 28 
 29     memset(num,0,sizeof(num));
 30 
 31     memset(flag,0,sizeof(flag));
 32 
 33     LCS();
 34 
 35     printf("%d
",num[strlen(a)][strlen(b)]);
 36 
 37     getLCS();
 38 
 39     return 0;
 40 
 41 }
 42 
 43  
 44 
 45 void LCS()
 46 
 47 {
 48 
 49     int i,j;
 50 
 51     for(i=1;i<=strlen(a);i++)
 52 
 53     {
 54 
 55         for(j=1;j<=strlen(b);j++)
 56 
 57         {
 58 
 59             if(a[i-1]==b[j-1])   ///注意这里的下标是i-1与j-1
 60 
 61             {
 62 
 63                 num[i][j]=num[i-1][j-1]+1;
 64 
 65                 flag[i][j]=1;  ///斜向下标记
 66 
 67             }
 68 
 69             else if(num[i][j-1]>num[i-1][j])
 70 
 71             {
 72 
 73                 num[i][j]=num[i][j-1];
 74 
 75                 flag[i][j]=2;  ///向右标记
 76 
 77             }
 78 
 79             else
 80 
 81             {
 82 
 83                 num[i][j]=num[i-1][j];
 84 
 85                 flag[i][j]=3;  ///向下标记
 86 
 87             }
 88 
 89         }
 90 
 91     }
 92 
 93 }
 94 
 95  
 96 
 97 void getLCS()
 98 
 99 {
100 
101  
102 
103     char res[500];
104 
105     int i=strlen(a);
106 
107     int j=strlen(b);
108 
109     int k=0;    ///用于保存结果的数组标志位
110 
111     while(i>0 && j>0)
112 
113     {
114 
115         if(flag[i][j]==1)   ///如果是斜向下标记
116 
117         {
118 
119             res[k]=a[i-1];
120 
121             k++;
122 
123             i--;
124 
125             j--;
126 
127         }
128 
129         else if(flag[i][j]==2)  ///如果是斜向右标记
130 
131             j--;
132 
133         else if(flag[i][j]==3)  ///如果是斜向下标记
134 
135             i--;
136 
137     }
138 
139  
140 
141     for(i=k-1;i>=0;i--)
142 
143         printf("%c",res[i]);
144 
145 }
146 
147

代码实现