一、學習目標

• 了解 Prefix Function / 失配函數（π / LPS） 的定義與線性建表 O(n)。
• 熟練用 KMP 做單一樣式的字串搜尋 O(n+m)（含重疊出現）。
• 能活用 π 陣列處理「邊界（border）」、「最長快樂前綴（同前綴後綴）」等題型。
• 清楚 KMP 與 Z-Function 的概念差異、何時選用哪一個。

二、觀念說明

π 陣列（prefix function）

pi[i] = 字串 s[0..i] 的最長真前綴，且同時是其後綴的長度。
例：s = "ababaca"
pi = [0,0,1,2,3,0,1]（常見教科書版本；也有以 1-based 表示者）

建表

j = pi[i-1]
while (j > 0 && s[i] != s[j]) j = pi[j-1];
if (s[i] == s[j]) j++;
pi[i] = j;

直觀理解：嘗試延伸目前匹配長度 j，失敗就「回退」到更短的 border 長度 pi[j-1] 再試。

KMP 搜尋：在長字串 T 中找 P

• 預處理 pi（針對 P）
• 掃 T 時用 j 表示目前已匹配的 P 前綴長度；遇到失配就用 pi[j-1] 回退。
• 每當 j == |P|，即命中一個出現位置；為允許重疊匹配，將 j = pi[j-1]。

Border（邊界）

同時是前綴與後綴的子字串。所有 border 長度可由 pi[n-1] 一路沿 pi[len-1] 追溯。

三、CSES實戰演練

題目1:String Matching

原題:
https://cses.fi/problemset/task/1753

題意:
給字串 T（text）與 P（pattern），求 P 在 T 中出現的次數（允許重疊）。

解題思路:

• 先對 P 建 π 陣列。
• 掃 T 時維護當前匹配長度 j；匹配成功到 |P| 即計數 +1，並把 j 回退為 pi[j-1] 以繼續找重疊解。

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string& s){
    int n = (int)s.size();
    vector<int> pi(n);
    for(int i=1;i<n;i++){
        int j = pi[i-1];
        while(j>0 && s[i]!=s[j]) j = pi[j-1];
        if(s[i]==s[j]) j++;
        pi[i]=j;
    }
    return pi;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string T, P; 
    if(!(cin >> T >> P)) return 0;
    auto pi = prefix_function(P);
    int j = 0, ans = 0;
    for(char c: T){
        while(j>0 && c!=P[j]) j = pi[j-1];
        if(c==P[j]) j++;
        if(j==(int)P.size()){
            ans++;
            j = pi[j-1]; // 允許重疊
        }
    }
    cout << ans << "\n";
    return 0;
}

題目2:Finding Borders

原題:
https://cses.fi/problemset/task/1732

題意:
給字串 s，輸出所有 border 長度（即同時為 s 的前綴與後綴的非空子字串長度），由小到大。若沒有，輸出空行。

解題思路:

• 對 s 建 π；令 len = pi[n-1]。
• 反覆將 len = pi[len-1] 直到 0，把過程中的長度收集起來，最後升冪列印。

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string& s){
    int n=(int)s.size(); vector<int> pi(n);
    for(int i=1;i<n;i++){
        int j=pi[i-1];
        while(j>0 && s[i]!=s[j]) j=pi[j-1];
        if(s[i]==s[j]) j++;
        pi[i]=j;
    }
    return pi;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string s; if(!(cin>>s)) return 0;
    auto pi = prefix_function(s);
    vector<int> lens;
    for(int len = pi.back(); len > 0; len = pi[len-1]) lens.push_back(len);
    sort(lens.begin(), lens.end());
    for(size_t i=0;i<lens.size();i++){
        if(i) cout << ' ';
        cout << lens[i];
    }
    cout << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Find the Index of the First Occurrence in a String

原題:
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

題意:
回傳 needle 在 haystack 中第一次出現的起始索引；若不存在回傳 -1。空字串按題意通常回傳 0。

解題思路:
經典 KMP：對 needle 建 π，掃 haystack 尋找第一個 j == |needle| 的位置即可。

class Solution {
    vector<int> prefix_function(const string& s){
        int n=s.size(); vector<int> pi(n);
        for(int i=1;i<n;i++){
            int j=pi[i-1];
            while(j>0 && s[i]!=s[j]) j=pi[j-1];
            if(s[i]==s[j]) j++;
            pi[i]=j;
        }
        return pi;
    }
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        auto pi = prefix_function(needle);
        int j=0;
        for(int i=0;i<(int)haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]) j=pi[j-1];
            if(haystack[i]==needle[j]) j++;
            if(j==(int)needle.size()){
                return i - j + 1;
            }
        }
        return -1;
    }
};

題目2:Longest Happy Prefix

原題:
https://leetcode.com/problems/longest-happy-prefix/

題意:
給字串 s，找出最長的非空字串，使它同時是 s 的前綴與後綴（不可等於整個字串），回傳該字串。

解題思路:

• 直接對 s 建 π。最長快樂前綴長度即 pi[n-1]。
• 回傳 s.substr(0, pi[n-1])。

class Solution {
    vector<int> prefix_function(const string& s){
        int n=s.size(); vector<int> pi(n);
        for(int i=1;i<n;i++){
            int j=pi[i-1];
            while(j>0 && s[i]!=s[j]) j=pi[j-1];
            if(s[i]==s[j]) j++;
            pi[i]=j;
        }
        return pi;
    }
public:
    string longestPrefix(string s) {
        auto pi = prefix_function(s);
        int len = pi.back();
        return s.substr(0, len);
    }
};