| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1096 人关注过本帖
标题:求助 字符串匹配 总是超时
只看楼主 加入收藏
baiyun198165
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2008-10-13
收藏
 问题点数:0 回复次数:3 
求助 字符串匹配 总是超时
题目:字符串匹配  

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]]
搜索更多相关主题的帖子: 字符 超时 
2008-10-13 23:29
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
这个用动态规划里的求最长公共子序列的方法应该可以吧。
我记得算法导论里有讲。
2008-10-16 13:31
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
#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;
}
2008-10-16 13:32
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
这个是我以前写的,当时那个串不超过1000,你改改试试看能过不。
2008-10-16 13:38
快速回复:求助 字符串匹配 总是超时
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029859 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved