POJ 2752：Seek the Name, Seek the Fame - KMP Next 數組應用

問題描述

給定字符串 S（長度 ≤ 400,000），求所有既是前綴又是後綴的子串長度（包含整個串），按遞增順序輸出。

核心思路：KMP 失配函數

KMP 的 next[i] 表示模式串前 i 個字符中，最長的既是真前綴又是真後綴的長度。遞歸應用：

• len = n 是整串，符合條件。
• len = next[n] 是最長真前綴後綴。
• len = next[next[n]] 是次長，以此類推直到 0。

收集所有 len > 0，反序輸出即為遞增序列。

代碼實現

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXL = 400010;
char s[MAXL];
int nxt[MAXL];

void build_next(const char* s, int len) {
    nxt[0] = -1;
    int i = 0, j = -1;
    while (i < len) {
        if (j == -1 || s[i] == s[j]) nxt[++i] = ++j;
        else j = nxt[j];
    }
}

int main() {
    while (scanf("%s", s) == 1) {
        int len = strlen(s);
        build_next(s, len);
        vector<int> ans;
        for (int k = len; k > 0; k = nxt[k]) ans.push_back(k);
        reverse(ans.begin(), ans.end());
        for (size_t i = 0; i < ans.size(); ++i) {
            if (i) putchar(' ');
            printf("%d", ans[i]);
        }
        puts("");
    }
    return 0;
}

複雜度

• 構建 next：O(n)。
• 收集答案：O(n)（最多 n 個邊界）。
• 總體 O(n)，線性時間。

總結

本題是 KMP next 數組的經典應用：「前綴後綴長度遞歸」直接給出所有合法長度。掌握 next 定義與遞歸跳轉是關鍵。