【題解】Simpsons'Hdden Talents HDU-2594⭐⭐ 【拡張KMP】

Simpsons'Hdden Talents HDU-2594
S 1のプレフィックスとS 2のサフィックスの《最大》が一致することを求めます.
Input
複数組の入力、1行目S 1、2行目S 2.S 1とS 2の長さは50000より小さいです.
Output
1行出力しますマッチしていない場合は、1つの0だけを出力します.これとは逆に、マッチングした文字列とマッチング長が出力されます.真ん中のスペースの間隔.
Examples
Sample Input clinton homer riemajorie Sample Output 0 rie 3
ベント
クイズ:
e-KMPのexted配列を容易に連想します.S[i...N-1]とTの最大プレフィックスマッチングを求めます.道e-KMPの裸問題です.しかし、細かい点に注意してください.ここでSの接頭辞とTのプレフィックスマッチングを要求します.exted[i]+i==Nの時だけ、接尾語として説明します.
上にはもっと簡単なやり方があるようですが、これも複雑ではないでしょう.
経験小結:

#include
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1 << 30;
const int maxn = 5e4 + 10;

char S[maxn], T[maxn];
int nxt[maxn], extend[maxn], N, M;
void getNext() {
    int a = 0, p = 0;
    nxt[0] = M;
    for (int i = 1; i < M; i++) {
        if (i >= p || i + nxt[i - a] >= p) {
            if (i >= p)
                p = i;
            while (p < M && T[p] == T[p - i])
                p++;
            nxt[i] = p - i;
            a = i;
        } else
            nxt[i] = nxt[i - a];
    }
}

void getExtend() {
    int a = 0, p = 0;
    getNext();
    for (int i = 0; i < N; i++) {
        if (i >= p || i + nxt[i - a] >= p) { //i>=p： S   T       
            if (i >= p)
                p = i;
            while (p < N && p - i < M && S[p] == T[p - i])
                p++;
            extend[i] = p - i;
            a = i;
        } else
            extend[i] = nxt[i - a];
    }
}
int main() {
    while(scanf("%s", T) != EOF){
        scanf(" %s", S);
        N = strlen(S), M = strlen(T);
        getExtend();
        int ans = 0, tag = 0;
        for(int i = 0; i < N; ++i)
            if(extend[i]+i==N && extend[i] > ans)
                ans = extend[i], tag = i;
        if(!ans)
            printf("0
");
        else{
            for(int i = tag; i < tag+ans; ++i)
                printf("%c",S[i]);
            printf(" %d
",ans);
        }
    }
    return 0;
}