C语言 最长公共子串

首先指出楼主的错误
最长的公共子字符串 应该改成 最长的连续公共子字符串
下面是符合楼主要求的参考代码
//作者:baihacker
//时间:9.12.2006
#include
#include

void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用来判断是否匹配的变量

for (i=1;i<=n;i++)//匹配长度的循环
for (j=0;j for (k=0;k {
count = 0;
for (l=0;l if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}

//作者:baihacker
//时间:9.12.2006
#include
#include

void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用来判断是否匹配的变量

for (i=1;i<=n;i++)//匹配长度的循环
for (j=0;j for (k=0;k {
count = 0;
for (l=0;l if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}

if (maxlength==0)
printf("No Answer");
else
for (i=0;i printf("%c",y[start+i]);
}

}
下面是真正的最长公共子串的动态规划算法
//作者:baihacker
//时间:9.12.2006

#include
#include

int b[50][50];
int c[50][50];

void lcs(x,m,y,n)
char *x;
int m;
char *y;
int n;
{
int i;
int j;

for (i=1;i<=m;i++) c[i][0] = 0;
for (i=1;i<=n;i++) c[0][i] = 0;
c[0][0] = 0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
if (x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}

}
}

void show(i,j,x)
int i;
int j;
char* x;
{
if (i==0||j==0)
return;
if (b[i][j]==1)
{
show(i-1,j-1,x);
printf("%c",x[i-1]);
}
else
if (b[i][j]==2)
show(i-1,j,x);
else
show(i,j-1,x);
}

void main()
{
char* x="aabcdababce";
char* y="12abcabcdace";
int m = strlen(x);
int n = strlen(y);
lcs(x,m,y,n);
show(m,n,x);

}

你在考我们那~？~？