首页 > ACM题库 > 九度OJ > 九度-1535-重叠的最长子串[扩展KMP]
2014
02-19

九度-1535-重叠的最长子串[扩展KMP]

题目来源九度 1535:2013年9月九度Online Judge程序猿求职及面试月赛第一场
题目描述:
给定两个字符串,求它们前后重叠的最长子串的长度,比如”abcde”和“cdefg”是”cde”,长度为3。
输入:
输入可能包含多个测试案例。
对于每个测试案例只有一行, 包含两个字符串。字符串长度不超过1000000,仅包含字符’a'-’z'。
输出:
对应每个测试案例,输出它们前后重叠的最长子串的长度。
样例输入:
abcde cdefg
样例输出:
3

 

扩展KMP算法的典型应用,不太好写。后面有个简单一些的代码。

#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
typedef long long lld;

const int INF=1000000000;

const int MAX=1000005;
int a[MAX];
int b[MAX];
char S[MAX],T[MAX];
void get_fail(char *S,char *T,int n,int m)
{
       int i,j=0;
       a[0]=m;
       while(1+j<m&&T[j]==T[1+j])j++;
       a[1]=j;
       int k=1;
       int need=0;
       for(i=2;i<m;i++)
       {
              need=k+a[k]-i;
              if(a[i-k]<need)a[i]=a[i-k];
              else
              {
                     j=0>need?0:need;
                     while(i+j<m&&T[j]==T[j+i])j++;
                     a[i]=j;
                     k=i;
              }
       }
       j=0;
       while(j<n&&j<m&&S[j]==T[j])j++;
       b[0]=j;
       k=0;
       for(i=1;i<n;i++)
       {
              need=k+b[k]-i;
              if(a[i-k]<need)b[i]=a[i-k];
              else
              {
                     j=0>need?0:need;
                     while(i+j<n&&j<m&&S[i+j]==T[j])j++;
                     b[i]=j;
                     k=i;
              }
       }
}

//start 提示:自动阅卷起始唯一标识,请勿删除或增加。
int main()
{  
       int n,m;
       int last=0;
       int i,j,k;

       while(scanf("%s%s",&S,&T)!=EOF)
       {
              n=strlen(S);
              m=strlen(T);
              get_fail(S,T,n,m);
              int ans=0;
              for(i=0;i<n;i++)
              {
                     if(b[i]==n-i)
                     {
                            ans=b[i];
                            break;
                     }
              }
              printf("%d\n",ans);
       }
    return 0;
}
//end //提示:自动阅卷结束唯一标识,请勿删除或增加。

/*
2 1
3 4

5 1
3 4 5 1 4

4 1
3 4 5 1
*/

解法2:

#include"stdio.h"
#include"string.h"
#define M 1000010
int judge(char *s,char *t,int low,int high){
    int index_t = 0;
    int len_t = strlen(t);
    while(low <= high)
    {
        if(s[low] != t[index_t]) return 0;
        ++low;
        ++index_t;
    }
    return 1;
}

int main()
{
    char s[M],t[M];
    int len_s,len_t,i,flag;
    while(~scanf("%s%s",s,t))
    {
        flag = 0;
        len_s = strlen(s);
        len_t = strlen(t);
        i = len_s > len_t ? len_s-len_t : 0;//减少判断,s串短,从0开始判断,s串长,从len_s-len_t位置开始判断。
        for(; i < len_s ;++i)
        {
            if(s[i] == t[0] && judge(s,t,i,len_s -1))
            {
                printf("%d\n",len_s - i);
                flag = 1;
                break;
            }
        }
        if(!flag) printf("0\n");
    }
    return 0;
}
/**************************************************************
    Problem: 1535
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:200 ms
    Memory:2904 kb
****************************************************************/

 

 


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。