最长公共子串

分类: 电脑/网络 >>程序设计 >>其他编程语言

问题描述:

编写一个程序，对输入的字符串s和t，求其最长的公共子字符串。

【输入形式】

从屏幕分行读大轿入串s和t。s和t由任意字符构成，长度都不超50个字符。输入数据确保只有唯一的最长公共子串。如果没有公共子串，打印No Answer

【输出形式】

在单独行滚液肆上输出串s和串t的最长公共子串，在结尾输出一个回车符。

算法提示：用一个int型的计数器记录当前匹配长度，用一个字符数组记录当前匹配子串，如果存在更长子串，则进行相应替换。

【样例说明】

假设从屏幕输入以下内容：

aabcdababce

12abcabcdace

则输出内容为：

abcda

用纯C解决！！

解析:

又是楼主?好像这个问题已经回答过了

下面的程序是符合楼主要求的程序

作者:baihacker

时间:9.12.2006

#include <stdio.h>

#include <string.h>

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=1i<=ni++)匹配长度的循环

for (j=0j<n-i+1j++)y的起始位置的循环

for (k=0k<m-i+1k++)x的起始位置的循环

{

count = 0

for (l=0l<il++)判断是否匹配,代码可以优化

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=0i<maxlengthi++)

printf("%c",y[start+i])

}

下面的程序是真正的最长公共子串的程序

作者:baihacker

时间埋皮:9.12.2006

#include <stdio.h>

#include <string.h>

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=1i<=mi++) c[i][0] = 0

for (i=1i<=ni++) c[0][i] = 0

c[0][0] = 0

for (i=1i<=mi++)

for (j=1j<=nj++)

{

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)

}

这是我们的程序设计题目，下面是运行成功的代码详细代码如下：#include <iostream.h>#include <iomanip.h>#define MAX 99 //定义最大的序列长度void main() { int i,j,m,n,t=0 char x[MAX]={' ',' '},y[MAX]={' ',' '伍伏},a[MAX][MAX]={' '} //初始化各序列数组，a[i][j]记录b[i][j]的得到方式 int b[MAX][MAX]={0} //b[i][j]记录序列xi和升戚yi的最长公共子序列的长度 char z[MAX]={' '} //初始化公共子序列数组 cout<<"****** 最大公共子序列求解 ******\n" cout<<"注意：字符串的长度腔笑携不要超过99!"<<endl cout<<"请输入第一个字符串的长度：m=" cin>>m cout<<"请输入第一个字符串:x["<<m<<"]=" for(i=1i<=mi++) cin>>x[i] //存入第一个序列 cout<<"请输入第二个字符串的长度：n=" cin>>n cout<<"请输入第二个字符串:y["<<n<<"]="//此处为计算最长公共子序列长度的动态规划算法 for(i=1i<=ni++) cin>>y[i] //存入第二个序列for(i=1i<=mi++)b[i][0]=0 //下面利用动态规划方法求解最长的公共子序列for(i=1i<=ni++)b[0][i]=0 for(i=1i<=mi++) for(j=1j<=nj++) { if(x[i]==y[j]) { b[i][j]=b[i-1][j-1]+1 a[i][j]='\\' //a[i][j]用3种符号标记3种情况 }else if(b[i-1][j]>=b[i][j-1]) //此处即为b[i][j]=Max（b[i][j-1],b[i-1][j] ） { b[i][j]=b[i-1][j]a[i][j]='|' }else{ b[i][j]=b[i][j-1]a[i][j]='-' } } //动态规划法到此处结束 /*cout<<"b[m][n]中的内容:\n" //此处显示动态规划描述过程，可省略for(i=0i<=mi++){ for(j=0j<=nj++) cout<<b[i][j]cout<<endl } cout<<"a[m][n]中的内容:\n"for(i=1i<=mi++) { for(j=1j<=nj++)cout<<a[i][j]cout<<endl}*///下面的算法实现根据数组a的内容打印出Xi与Yj的最长公共子序列。i=m,j=nwhile(1) {if(i==0||j==0) breakif(a[i][j]=='\\'){z[t++]=x[i]//反序记录最长公共子序列到z中i=i-1,j=j-1}elseif(a[i][j]=='|')i=i-1 elsej=j-1} cout<<"\n序列x["<<m<<"]和序列y["<<n<<"]的最长公共子序列为:"for(i=t-1i>=0i--) //输出最长公共子序列 if(i==t-1) { if(t==1) {cout<<"LCS:<"<<z[i]<<">"} else {cout<<"LCS:<"<<z[i]} } else { if(i==0) cout<<","<<z[i]<<">" else cout<<","<<z[i] }cout<<"\n"<<"此最长公共子序列的长度为:"<<b[m][n]<<endlcout<<"\n"<<endl}

---