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


基本思想还是以前的求解方法：对于字符串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

#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX 100void LCSLength(char *x,char *y,int m,int n,int c[][MAX],int b[][MAX]);void LCS(int i ,int j, char *x ,int b[][MAX]);int main(void){    char *arr1 = NULL;    char *arr2 = NULL;    int b[MAX][MAX] = {0};    int c[MAX][MAX] = {0};    int max1,max2;                    /* 定义两个字符串的长度*/    max1 = max2 =0;    printf("请输入第一个字符串的长度：");    scanf("%d",&max1);    getchar();                       /* 为了吸收按下的那个换行符，此时它存在输入缓冲区                                      在两个连续的scanf()中必须用*/    arr1 = (char *)malloc(sizeof(char) * max1);    printf("请输入arr1的%d个字符：",max1);    for(int i = 0; i < max1; i++)        scanf("%c", &arr1[i]);    printf("请输入第二个字符串的长度：");    scanf("%d",&max2);    arr2 = (char *)malloc(sizeof(char) * max2);    printf("请输入arr2的%d个字符：",max2);    for(int j = 0; j < max2; j++)        scanf("%c", &arr2[j]);    printf("最长公共子序列是：");    LCSLength(arr1,arr2,max1,max2,c,b);    LCS(max1,max2,arr1,b);    printf("\n");    free(arr1);    free(arr2);    return 0;}void LCSLength(char *x,char *y,int m,int n,int c[][MAX],int b[][MAX]) {    int i ,j;    for (i = 1; i <= m; i++)         c[i][0] = 0;    for (i = 1; i <= n; i++)         c[0][i] = 0;    for (i = 1; i <= m; i++)        for (j = 1; j <= n; j++)        {            if (x[i - 1] == y[j])            {                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 LCS(int i ,int j, char *x ,int b[][MAX]){    if (i ==0 || j== 0) return;    if (b[i][j] == 1)    {        LCS(i - 1,j - 1,x,b);        printf("%c",x[i - 1]);    }    else if (b[i][j] == 2)        LCS(i - 1,j,x,b);    else         LCS(i,j - 1,x,b);}
[解决办法]
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;} 
 
[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出