计算重叠最长子串问题

问题：给定两个字符串，求它们前后重叠的最长子串的长度，比如”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;
              }
       }
}

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 ",ans);
       }
    return 0;
}

方法二：

#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 ",len_s - i);
                flag = 1;
                break;
            }
        }
        if(!flag) printf("0 ");
    }
    return 0;
}