#include "stdafx.h"
/*
求兩個字符串的最大公共子串的問題（簡要說明，從另外一個地方轉(zhuǎn)的，和下面一篇合成在一起）：
把字符串1（長度m）橫排，串2（長度n）豎排，得到一個m×n的矩陣c，矩陣的每個元素的值如下，如果m[i]=n[j]，則c[j][i]=1,否則，c[j][i]=0。然后找出矩陣中連續(xù)是1的對角線最長的一個，則對角線的長度就是公共子串的長度.
LCS問題就是求兩個字符串最長公共子串的問題。解法就是用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對角線最長的1序列，其對應(yīng)的位置就是最長匹配子串的位置。
下面是字符串babhbxbhhaahbz和字符串hababhbbhzzx的匹配矩陣，前者為X方向的，后者為Y方向的。不難找到，紅色部分是最長的匹配子串。通過查找位置我們得到最長的匹配子串為：babhb
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對角線序列又要花去一定的時間。
通過改進矩陣的生成方式和設(shè)置標(biāo)記變量，可以省去這部分時間。
下面是新的矩陣生成方式：
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
不用多說，你大概已經(jīng)看出來了。當(dāng)字符匹配的時候，我們并不是簡單的給相應(yīng)元素賦上1，而是賦上其左上角元素的值加一。我們用兩個標(biāo)記變量來標(biāo)記矩陣中值最大的元素的位置，在矩陣生成的過程中來判斷當(dāng)前生成的元素的值是不是最大的，據(jù)此來改變標(biāo)記變量的值，那么到矩陣完成的時候，最長匹配子串的位置和長度就已經(jīng)出來了。
這樣做速度比較快，但是花的空間太多。
*/
char* lcs(char *str1, char *str2,int* p_length)
{
int i,j,m,n,length,x,y;
m = strlen(str1)+1;
n = strlen(str2)+1;
int **matrix = new int*[m];
for(i = 0; i < m; i++)
matrix[i] = new int[n];
for(i = 0; i < m; i++)
matrix[i][0]=0;//第0列都初始化為0
for(j = 0; j < n; j++)
matrix[0][j]=0;//第0行都初始化為0
length = -1;
*p_length = -1;
for(i = 1 ; i < m ; i++)
{
for(j = 1; j < n; j++)
{
if(str1[i-1]==str2[j-1])
{
//只需要跟左上方的matrix[i-1][j-1]比較就可以了
matrix[i][j]=matrix[i-1][j-1]+1;
}
else{
//不連續(xù)的時候還要跟左邊的matrix[i][j-1]、上邊的matrix[i-1][j]值比較，這里不需要
matrix[i][j]=0;
}
if(matrix[i][j]>length)
{
length=matrix[i][j];
x=i;
y=j;
}
}
}
for(i = 0; i < m; i++)
delete[] matrix[i];
delete[] matrix;
if (length>0)
{
*p_length = length;
return &str1[x-length];
}
return NULL;
}
int main(void)
{
char str1[1000],str2[1000],str3[1000];
int length;
printf("請輸入第一個字符串：");
gets(str1);
printf("請輸入第二個字符串：");
gets(str2);
char* pszText = lcs(str1, str2,&length);
printf("最長公共連續(xù)子串的長度為：%d\n",length);
if (pszText!=NULL)
{
strncpy(str3,pszText,length);
str3[length] = 0;
printf("最長公共連續(xù)子串：%s\n",str3);
}
system("pause");
return 0;
}