Description

给你2个字符串(可能包括数字以及标点)，长度<=50124，请你求出最长的连续的公共子序列。

Input

输入有2个字符串A，B, 各占一行。

Output

输出字符串A和B的最长连续公共子序列的长度L。

Sample Input

aaa
aba
 

Sample Output

1
请给个C算法
测试地址http://202.120.80.191/problem.php?problemid=1805

两个字符串 A，B
先将A和B中较短的字符串找出来

定义最长连续公共子序列的长度L为0；
定义初始长度Len为0
将短的字符串的第一位与长的字符串的第一位比较，若字符相等，则Len+1，若不相等，则Len赋给L，Len复位为0；
继续比较两个字符串的第二位，直到短字符串的最后一位。

再将短的字符串的第一位与长的字符串的第二位比较

依次类推

当短字符串的最后一位与长字符串的最后一位比较完毕后，
输出L的值即可。

/*********************************************************/
//文件名：StringCompare.cpp
//程序作者：王丰元
//版本:V1.0
//功能：求两个字符串的最长连续公共子序列的长度
/********************************************************/
 


#include<stdio.h>
#include<string.h>
#define MAX 50124

unsigned int StringCompare(char *a,char *b)
//输入：两个字符串a,b;
//输出：最长连续公共子序列的长度
//算法描述例子：
//  a:  34567
//  b:  123456789
//34567与    1比较,LMax=0;
//34567与   12比较,Lmax=0;
//34567与  123比较,LMax=0;
//34567与 1234比较,LMax=0;
//34567与12345比较,LMax=0;
//34567与23456比较,LMax=0;
//34567与34567比较,Lmax=5;
//34567与45678比较,LMax=5;
//34567与56789比较,LMax=5;
//34567与6789 比较,LMax=5;
//34567与789  比较,LMax=5;
//34567与89   比较,Lmax=5;
//34567与9    比较,LMax=5;
//最差状态一共比较5+9-1=13次
//实际上对于本例，在第7次比较之后，由于Lmax==5,故停止比较，
{
     long int la=strlen(a);
     long int lb=strlen(b);
     long int lc=la<lb?la:lb;
     long int i,j;
     long int LMax=0;
     long int Len=0;
     
     for(i=1-la;i<lb;i++)
     {
          Len=0;
          for(j=0;j<la;j++)
          {
               if((i+j>=0)&&(i+j<lb)&&(*(a+j)==*(b+i+j)))
               {
                    Len++;
               }else
               {
                    if(Len>LMax) LMax=Len;
                    if(LMax==lc) break;
                    Len=0;
               }
          }
          if(Len>LMax) LMax=Len;
          if(LMax==lc) break;
    }   
    return LMax;
}

int main(void)
{
    char a[MAX];
    char b[MAX];
    printf("输入字符串A:\n");
    scanf("%s",a);
    printf("输入字符串B:\n");   
    scanf("%s",b);
    printf("最长连续公共子序列的长度为:%d\n",StringCompare(b,a));
    getchar();
    getchar();
    return 0;
}

[[italic] 本帖最后由 qq95620412 于 2008-1-1 03:33 编辑 [/italic]]