hdu 2594 Simpsons’ Hidden Talents（两个串的next数组）

题意：两个字符串s、t，求s和t的最长的相同的前缀和后缀

思路：先求s的next数组，再求t的next数组（即代码中ex数组，此时不是自己与自己匹配，而是与s匹配），最后看ex[len2]即可（len2为串t的长度）。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

#define MaxSize 50005

int _next[MaxSize],ex[MaxSize];

void GetNext(char t[]){//求next数组
    int j,k,len;
    j=0;
    k=-1;
    _next[0]=-1;
    len=strlen(t);
    while(j<len){
        if(k==-1||t[j]==t[k]){
            ++j;
            ++k;
            _next[j]=k;//此句可由优化替代
            /*优化（仅保证求KMPIndex时可用。谨慎使用。）
            if(t[j]!=t[k])next[j]=k;
            else next[j]=next[k];
            */
        }
        else k=_next[k];
    }
}

void Get_ex(char s[],char t[]){//求ex数组
    GetNext(s);
    int j,k,len;
    j=0;
    k=0;
    ex[0]=0;
    len=strlen(t);
    while(j<len){
        if(k==-1||t[j]==s[k]){
            ++j;
            ++k;
            ex[j]=k;//此句可由优化替代
            /*优化（仅保证求KMPIndex时可用。谨慎使用。）
            if(t[j]!=t[k])next[j]=k;
            else next[j]=next[k];
            */
        }
        else k=_next[k];
    }
}

int main(){
    char str1[MaxSize],str2[MaxSize];
    int i,len2;
    while(~scanf("%s%s",str1,str2)){
        Get_ex(str1,str2);//求ex数组
        len2=strlen(str2);
        if(ex[len2]==0)printf("0
");
        else{
            for(i=0;i<ex[len2];++i)
                printf("%c",str1[i]);
            printf(" %d
",ex[len2]);
        }
    }
    return 0;
}