求最长公共子串 递归写的

求助 求最长公共子串 递归写的
程序运行不过 帮我看看哪里错误了


基本思想还是以前的求解方法：对于字符串a,b,尽量用b的最大的子字符串c去匹配另外一个字符串a，如果c不是a的子串，那么用字符串b的长度比b少1的子串去匹配a,直到匹配到了为止或者子串的长度为0．



#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;

int LCString(char *s1,char *s2)//char型指针，其指向一个字符串
{
char temp[255];
int start,count=-1,len1=strlen(s1),len2=strlen(s2);
for(start=0;start+len2<len1;start++)
{
cout<<"进入LCString"<<endl<<"start="<<start<<endl;
for(count=0;count<len2;count++)
{
if(s1[start+count]!=s2[count])
break;
}
if(count>=len2)//在s1中找到一个子串和当次传入s2相同
break;
}
if(count>=len2)//如果s2是s1的子串
return len2;
//把s2中后当前len2-1个字符构成的串与s1比较
//输出后半
cout<<"后半";
len1=LCString(s1,s2+1);
//把s2中前当前len2-1个字符构成的串与s1比较
strncpy(temp,s2,len2-1);
temp[len2-1]='/0';
//输出前半
cout<<"前半";
len2=LCString(s1,temp);
//返回前后两段比较得到的LCString中较大的
return len1>len2?len1:len2;
}
int main()
{
char *s1="xzyzzyx" ;
char *s2="zzyzzyx";
cout<<"LCString="<<LCString(s1,s2)<<endl;
return 0;
}

[解决办法]

C/C++ code

//最长公共子序列字符个数//c[i][j]保存字符串 {xi},{yj},(长度分别为i,j)的最长公共子序列的字符个数//i=0或者是j=0 时，c[i][j]必定为零, i,j>=0 且 xi=yj, c[i][j]=c[i-1][j-1]+1//若 i,j>0 但xi!=yj, c[i][j]=max{ c[i-1][j] , c[i][j-1] }#include <stdio.h>#include <string.h>int c[1001][1001];void lcs(int a, int b, char x[], char y[], int c[][1001]) {    int i,j;    for(i=1;i<a;i++)        c[i][0]=0; //if b==0, set c[i][j]=0;    for(i=1;i<b;i++)        c[0][i]=0; // if a==0; set c[i][j]=0;    for(i=1;i<=a;i++) // if a!=0,b!=0 loop        for(j=1;j<=b;j++) {            if(x[i-1]==y[j-1])                c[i][j]=c[i-1][j-1]+1;            else if (c[i-1][j]>=c[i][j-1])                c[i][j]=c[i-1][j];            else                c[i][j]=c[i][j-1];        }}int main() {    char x[1001],y[1001];    while ( scanf("%s%s",x,y)!=EOF ) {        int a=strlen(x);        int b=strlen(y);        memset(c,0,sizeof(c));        lcs(a,b,x,y,c);        printf("%d\n",c[a][b]);    }    return 0;}
[解决办法]
http://hi.baidu.com/erennetwork/blog/item/9eee5eca134cea0401e92880.html

楼主参考一下这个链接的内容