#include "stdafx.h"
/*
求兩個(gè)字符串的最大公共子串的問題（簡要說明，從另外一個(gè)地方轉(zhuǎn)的，和下面一篇合成在一起）：
把字符串1（長度m）橫排，串2（長度n）豎排，得到一個(gè)m×n的矩陣c，矩陣的每個(gè)元素的值如下，如果m[i]=n[j]，則c[j][i]=1,否則，c[j][i]=0。然后找出矩陣中連續(xù)是1的對(duì)角線最長的一個(gè)，則對(duì)角線的長度就是公共子串的長度.
LCS問題就是求兩個(gè)字符串最長公共子串的問題。解法就是用一個(gè)矩陣來記錄兩個(gè)字符串中所有位置的兩個(gè)字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對(duì)角線最長的1序列，其對(duì)應(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對(duì)角線序列又要花去一定的時(shí)間。
通過改進(jìn)矩陣的生成方式和設(shè)置標(biāo)記變量，可以省去這部分時(shí)間。
下面是新的矩陣生成方式：
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)字符匹配的時(shí)候，我們并不是簡單的給相應(yīng)元素賦上1，而是賦上其左上角元素的值加一。我們用兩個(gè)標(biāo)記變量來標(biāo)記矩陣中值最大的元素的位置，在矩陣生成的過程中來判斷當(dāng)前生成的元素的值是不是最大的，據(jù)此來改變標(biāo)記變量的值，那么到矩陣完成的時(shí)候，最長匹配子串的位置和長度就已經(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ù)的時(shí)候還要跟左邊的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("請(qǐng)輸入第一個(gè)字符串：");
gets(str1);
printf("請(qǐng)輸入第二個(gè)字符串：");
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;
}