HDU 2954 Simpsons' Hidden Talents：KMP 求最長前綴後綴

題目

給兩字符串 s1、s2，找最長字符串同時是 s1 的前綴和 s2 的後綴。輸出該串及其長度。

KMP 核心技巧

將 s1 和 s2 首尾拼接：S = s1 + s2。
對 S 計算 next 數組（最長公共前後綴長度）。
最終答案長度 = min(next[|S|], |s1|, |s2|)。
原理：next[|S|] 給出 S 的最長真前綴 = 真後綴，此前綴屬於 s1，後綴屬於 s2，長度不超過兩串長度。

C 代碼

#include 
#include 
#define MAXN 100005

char s1[MAXN], s2[MAXN];
int nxt[MAXN];

void getNext(char* s, int len) {
    int p = 0;
    nxt[1] = 0;
    for (int i = 2; i <= len; ++i) {
        while (p > 0 && s[p] != s[i-1]) p = nxt[p]; // 0-based 字符串調整
        if (s[p] == s[i-1]) ++p;
        nxt[i] = p;
    }
}

int main() {
    while (scanf("%s%s", s1, s2) == 2) {
        int n = strlen(s1), m = strlen(s2);
        // 拼接到 s1 後
        strcpy(s1 + n, s2);
        getNext(s1, n + m);
        int ans = nxt[n+m];
        if (ans > n) ans = n;
        if (ans > m) ans = m;
        for (int i = 0; i < ans; ++i) putchar(s1[i]);
        if (ans) printf(" %d\n", ans);
        else puts(" 0");
    }
    return 0;
}

關鍵點

• 字符串下標處理：代碼中 s 從 1 開始存儲，getNext 內部對應調整。
• next[i] 定義為 s[1..i] 的最長真前綴 = 真後綴長度。
• 拼接後總長 ≤ 2×10⁵，O(N) KMP 極快。

複雜度

• 時間：O(|s1| + |s2|)。
• 空間：O(|s1| + |s2|)。

總結

利用 KMP next 數組的「前綴=後綴」特性，將雙串問題轉化為單串問題，是字符串算法中極具技巧性的應用。同類問題：最長回文前綴、字符串周期檢測等。