2016 UESTC Training for Search Algorithm&String K-卿おじいさんの3人の彼女KMP、ジャンプ配列

K-卿おじいさんの3人の彼女
Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit  Status
卿おじいさんは文字列を見つけて、彼は上に$3$の彼女の名前を見つけようとした.彼の彼女の名前は文字列の接頭辞で、一つは接尾辞で、もう一つは真ん中にあります.
ある位置(三者は重ならない).彼はあなたに彼女の名前の最大長さを教えてあげたいと思っています.つまり、最も長い子列を見つけて接頭辞で接尾辞であり、
まだ真ん中で、この子列の長さを求めます.
Input
1行目の数字N(N<=100)は、N組のデータを表す.次のN行は、行ごとに1文字列s,1<=|s|<=100000であり、いずれも小文字で構成される.
Output
各セットのデータについて、最も長い条件を満たすサブ列の長さを出力します.
Sample input and output
Sample Input
Sample Output

5
xy
abc
aaa
aaaaba
aaxoaaaaa

0
0
1
1
2

   
  Source
     2016 UESTC Training for Search Algorithm & String
  My Solution
KMPのジャンプ配列の拡張使用の鍵はKMP思考の転化にある.思考が重要だ!まずテキスト列でジャンプ配列を作ります.テキスト列の長さをlenとします.私たちはlen番目の位置に一致することを考慮します.ジャンプ配列はジャンプごとに位置します.テキスト列の接頭辞=接尾辞を保証し、自分で手動でシミュレーションして描くことができます.したがって、残りの中間部分に一致するサブストリングがあるかどうかを探すだけでよい.見つけたらいいのに、これが一番長い^^.複雑度O(T*n)

#include
#include
#include
using namespace std;
const int maxn=1e5 + 8;

int nxt[maxn], len;
char text[maxn];
void getnxt(char *p)
{
    nxt[1] = 0;
    for(int i = 1, j = 0; i < len; i++){
        j = nxt[i];
        while(j && p[j] != p[i])
            j = nxt[j];
        nxt[i+1] = p[j] == p[i] ? j+1 : 0;            //         ，        memset 
    }
}

bool kmp(char *T,char *P,int n,int m)
{
    for(int i=0, j=0; i < n; i++){
        while(j && P[j] != T[i])
            j = nxt[j];
        if(P[j] == T[i])
            j++;
        if(j == m)
            return true;
    }
    return false;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int T,j,ans;

    scanf("%d",&T);
    while(T--){
        ans=0;
        scanf("%s",text);
        len=strlen(text);
        getnxt(text);
        j = nxt[len];
        while(j){
            if(len >= 3*j&& kmp(text+j, text, len-2*j, j)){
                ans=j;
                break;
            }
            j = nxt[j];
        }
        printf("%d
",ans);
    }
    return 0;
}

Thank you!
                                                                                                                                               ------from ProLights