最長公共子串(LCS),有三種情況:1.公共子串的元素必須相鄰. 2.公共子串的元素可以不相鄰聯單3. 求多個字符串而不是兩個字符串的最長公共子串
1.公共子串的元素必須相鄰:
LCS問題就是求兩個字符串最長公共子串的問題。解法就是用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況，若是匹配則為1，否則為0。然後求出對角線最長的1序列，其對應的位置就是最長匹配子串的位置.
下面是字符串21232523311324和字符串312123223445的匹配矩陣，前者為X方向的，後者為Y方向的。不難找到，紅色部分是最長的匹配子串。通過查找位置我們得到最長的匹配子串為：21232
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但是在0和1的矩陣中找最長的1對角線序列又要花去一定的時間。通過改進矩陣的生成方式和設置標記變量，可以省去這部分時間。下面是新的矩陣生成方式：
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
當字符匹配的時候，我們並不是簡單的給相應元素賦上1，而是賦上其左上角元素的值加一。我們用兩個標記變量來標記矩陣中值最大的元素的位置，在矩陣生成的過程中來判斷當前生成的元素的值是不是最大的，據此來改變標記變量的值，那麼到矩陣完成的時候，最長匹配子串的位置和長度就已經出來了。
算法的基本思想：
當字符匹配的時候，不是簡單的給相應元素賦上1，而是賦上其左上角元素的值加一。
我們用兩個標記變量來標記矩陣中值最大的元素的位置，在矩陣生成的過程中來判斷
當前生成的元素的值是不是最大的，據此來改變標記變量的值，那麼到矩陣完成的時
候，最長匹配子串的位置和長度就已經出來了。
[cpp]
#include<stdio.h>
#include<string.h>
#define N 100
//LCS問題就是求兩個字符串最長公共子串的問題
char *LCS(char *a,char *b)
{
int len_a = strlen(a); //獲取字串的長度
int len_b = strlen(b);
char *p;
int c[N][N] = {0}; //矩陣c記錄兩串的匹配情況
int start,end,len,i,j; //start表明最長公共子串的起始點，end表明最長公共子串的終止點
end = len = 0; //len表明最長公共子串的長度
for(i=0;i<len_a;i++) //串開始從前向後比較
{
for(j=0;j<len_b;j++)
{
if(a[i] == b[j])
if(i == 0 || j == 0)
c[i][j] = 1;
else
c[i][j] = c[i-1][j-1] + 1;
// else
// c[i][j] = 0;
if(c[i][j] > len)
{
len = c[i][j];
end = j;
}
}
}
start = end - len + 1;
p = (char *)malloc(len+1); //數組p記錄最長公共子串
for(i=start;i<=end;i++)
p[i-start] = b[i];
p[len] = '\0';
for(j=0;j<len_b;j++)
{
for(i=0;i<len_a;i++)
printf("%2d",c[i][j]);
printf("\n");
}
return p;
}
int main(int argc,char *argv[])
{
char str1[N],str2[N];
printf("請輸入字符串1：");
gets(str1);
printf("請輸入字符串2：");
gets(str2);
printf("最長子串為：%s\n",LCS(str1,str2));
return 0;
}
注意：該算法只能打印出最長公共子串的一個，而不是全部解。
