HDU 2594 Simpsons' Hidden Talents——KMP 尋找最長公共前後綴

問題描述

給兩字符串 A, B（長度 ≤ 50000）。求 B 的最長前綴，使其同時是 A 的後綴。輸出該前綴（逆序）及其長度。若無公共部分輸出 0。多測試用例，EOF 結束。

核心轉化

設 `A_rev = reverse(A)`, `B_rev = reverse(B)`。
原問題「B 的前綴 = A 的後綴」⇔ 「`B_rev` 的後綴 = `A_rev` 的前綴」。
即求 `B_rev` 在 `A_rev` 中作為前綴的最長匹配長度。
這正是 KMP 匹配 `A_rev`（文本）與 `B_rev`（模式）時，最終匹配到的長度 `j`。

KMP 流程

1. 構建 `B_rev` 的 `fail` 數組（next 數組）。
2. 在 `A_rev` 上跑 KMP，記錄匹配長度 `j`。
3. 匹配結束時 `j` 即為最長公共長度。該公共串為 `B_rev[0..j-1]`，逆序輸出即原順序。

代碼實現

#include 
using namespace std;
const int MAXN = 50010;
char A[MAXN], B[MAXN], revA[MAXN], revB[MAXN];
int fail[MAXN];

void buildFail() {
    int m = strlen(revB);
    fail[0] = fail[1] = 0;
    for (int i = 1; i < m; ++i) {
        int j = fail[i];
        while (j && revB[j] != revB[i]) j = fail[j];
        fail[i+1] = (revB[j] == revB[i]) ? j+1 : 0;
    }
}

int main() {
    while (fgets(A, MAXN, stdin) && A[0] != '\n') {
        fgets(B, MAXN, stdin);
        int n = strlen(A); if (A[n-1]=='\n') A[--n]=0;
        int m = strlen(B); if (B[m-1]=='\n') B[--m]=0;
        for (int i = 0; i < n; ++i) revA[i] = A[n-1-i];
        for (int i = 0; i < m; ++i) revB[i] = B[m-1-i];
        revA[n] = revB[m] = 0;
        buildFail();
        int j = 0;
        for (int i = 0; i < n; ++i) {
            while (j && revA[i] != revB[j]) j = fail[j];
            if (revA[i] == revB[j]) ++j;
        }
        if (j == 0) puts("0");
        else {
            for (int i = j-1; i >= 0; --i) putchar(revB[i]);
            printf(" %d\n", j);
        }
    }
    return 0;
}

關鍵點

• 雙逆序轉化：將「前綴=後綴」轉為標準 KMP「模式前綴匹配文本前綴」。
• fail 數組構建：標準 KMP，`fail[i]` = 模式前 i 字符最長真前綴=真後綴長度。
• 輸入讀取：`fgets` 讀整行含空格，去換行符。
• 輸出逆序：匹配的是逆序串，輸出時再逆序回原順序。

複雜度

• 時間：O(|A|+|B|) 每測試用例。
• 空間：O(|B|)。

總結

KMP 經典讛體：「A的後綴 = B的前綴」雙逆序轉為標準匹配。構建模式串 fail，掃描文本得匹配長度，逆序輸出。掌握此轉化，可解決所有「前綴後綴匹配」變體。