题目：字符串匹配  

Time Limit:1000MS Memory Limit:30000KB
Total Submit:333 Accepted:27

Description

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

Input

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

Output

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

Sample Input

aaa
aba
 

Sample Output

1


Source

我的程序：
#include<stdio.h>
#include<string.h>
#define MAX 50124
unsigned int StringCompare(char *a,char *b)
{
     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()
{
    char a[MAX];
    char b[MAX];
    scanf("%s",&a);   
    scanf("%s",&b);
    printf("%d\n",StringCompare(b,a));
    getchar();getchar();
    return 0;
}
总是超时
哪位高手来解答一下~！！
谢谢

[[it] 本帖最后由 baiyun198165 于 2008-10-13 23:31 编辑 [/it]]

这个用动态规划里的求最长公共子序列的方法应该可以吧。
我记得算法导论里有讲。

#include<stdio.h>
#include<memory.h>
#include<string.h>
int dp[1000+1][1000+1];
int main(){
    int m,n,i,j;
    char x[1000+1],y[1000+1];
    while(scanf("%s%s",&x,&y)!=-1){
         m=strlen(x);
         n=strlen(y);
         memset(dp,0,sizeof(dp));
         for(i=1;i<=m;i++){
            for(j=1;j<=n;j++){
               if(x[i-1]==y[j-1])
                  dp[i][j]=dp[i-1][j-1]+1;
               else
                  dp[i][j]=dp[i][j-1]>dp[i-1][j]?dp[i][j-1]:dp[i-1][j];
            }
         }
         printf("%d\n",dp[m][n]);
    }
    return 0;
}

这个是我以前写的，当时那个串不超过1000，你改改试试看能过不。