#include "stdafx.h"
/*
求两个字符串的最大公共子串的问题（简要说明，从另外一个地方转的，和下面一篇合成在一起）：
把字符串1（长度m）横排，串2（长度n）竖排，得到一个m×n的矩阵c，矩阵的每个元素的值如下，如果m[i]=n[j]，则c[j][i]=1,否则，c[j][i]=0。然后找出矩阵中连续是1的对角线最长的一个，则对角线的长度就是公共子串的长度.
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置。
下面是字符串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对角线序列又要花去一定的时间。
通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。
下面是新的矩阵生成方式：
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，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。
这样做速度比较快，但是花的空间太多。
*/
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{
//不连续的时候还要跟左边的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("最长公共连续子串的长度为：%d\n",length);
if (pszText!=NULL)
{
strncpy(str3,pszText,length);
str3[length] = 0;
printf("最长公共连续子串：%s\n",str3);
}
system("pause");
return 0;
}