String-Matching

這篇在解決什麼

「在長度 n 的文字裡找長度 m 的樣式」，暴力是 O(nm)。三個標準工具都能做到 O(n + m)，但它們回答的問題不只是「有沒有出現」：

• KMP 的副產品 pi[] 回答「每個前綴的最長 border 是多長」——週期、循環節、最短補全都靠它
• Z-function 的 z[] 回答「從每個位置開始，和整個字串的最長共同前綴多長」
• 字串雜湊回答「任兩個子字串相不相等」，O(1) 一次，代價是有碰撞機率

這篇三個都收，並實測雜湊被打爆的確切條件。對拍暴力驗過：KMP 與 Z 的搜尋結果、pi[] 與 z[] 的定義式、雜湊比對，各 4000 組隨機字串全過。

KMP — pi[i] 是「s[0..i] 的最長真 border」

border = 既是前綴又是後綴的字串（不含自己）。

s  =  a  b  a  c  a  b  a  b
i     0  1  2  3  4  5  6  7
pi    0  0  1  0  1  2  3  2

pi[6] = 3：s[0..6] = "abacaba" 的最長 border 是 "aba"
           a b a c a b a
           └──┬──┘ └──┬──┘
             "aba"   "aba"      前綴和後綴重疊也沒關係

失配時就是靠這個往回跳：已經匹配了 j 個字元卻在第 j+1 個失配，
不必從頭再來，跳到 pi[j-1] 繼續即可——因為那 pi[j-1] 個字元一定也匹配。

// Time: O(n)   Space: O(n)
vector<int> prefixFunction(const string& s) {
  int n = s.size();
  vector<int> pi(n, 0);
  for (int i = 1; i < n; ++i) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) {
      j = pi[j - 1];  // 失配就退到次長的 border 再試
    }
    if (s[i] == s[j]) {
      ++j;
    }
    pi[i] = j;
  }
  return pi;
}

// 找出 pat 在 text 中所有出現位置（0-indexed 起點）
vector<int> kmpSearch(const string& text, const string& pat) {
  vector<int> res;
  if (pat.empty()) {
    return res;
  }
  string s = pat + '\x01' + text;  // 分隔符必須是兩邊都不會出現的字元
  auto pi = prefixFunction(s);
  int m = pat.size();
  for (int i = m + 1; i < (int)s.size(); ++i) {
    if (pi[i] == m) {
      res.push_back(i - 2 * m);
    }
  }
  return res;
}

Z-function — z[i] 是「s 和 s[i..] 的最長共同前綴」

s  =  a  a  b  x  a  a  y  a  a
i     0  1  2  3  4  5  6  7  8
z     9  1  0  0  2  1  0  2  1
      ↑
   z[0] 定義成 n（或不使用）

z[4] = 2：從位置 4 開始的 "aay.." 和開頭的 "aab.." 共同前綴是 "aa"

// Time: O(n)   Space: O(n)
vector<int> zFunction(const string& s) {
  int n = s.size();
  vector<int> z(n, 0);
  if (n) {
    z[0] = n;
  }
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i < r) {
      z[i] = min(r - i, z[i - l]);  // 借用先前算過的區段，免掉重複比較
    }
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
      ++z[i];
    }
    if (i + z[i] > r) {
      l = i;
      r = i + z[i];  // 維護「最右邊的匹配區段」
    }
  }
  return z;
}

搜尋一樣用拼接：z[i] >= m 的位置就是一次出現。

字串雜湊 — O(1) 比較任兩個子字串

把字串看成 base 進位的數：h(s) = s[0]·B^(n-1) + s[1]·B^(n-2) + … + s[n-1]，取模避免溢位。前綴雜湊算好之後，任意子字串的雜湊是 O(1)：

// build: O(n)   get: O(1)
// 雙模：兩個模數同時碰撞的機率才是問題，見下面實測
struct StringHash {
  static const long long M1 = 1000000007, M2 = 998244353, B1 = 131, B2 = 137;
  vector<long long> h1, h2, p1, p2;

  explicit StringHash(const string& s) {
    int n = s.size();
    h1.assign(n + 1, 0);
    h2.assign(n + 1, 0);
    p1.assign(n + 1, 1);
    p2.assign(n + 1, 1);
    for (int i = 0; i < n; ++i) {
      h1[i + 1] = (h1[i] * B1 + s[i]) % M1;
      h2[i + 1] = (h2[i] * B2 + s[i]) % M2;
      p1[i + 1] = p1[i] * B1 % M1;
      p2[i + 1] = p2[i] * B2 % M2;
    }
  }

  pair<long long, long long> get(int l, int r) {  // 閉區間 [l, r]
    long long a = ((h1[r + 1] - h1[l] * p1[r - l + 1]) % M1 + M1) % M1;
    long long b = ((h2[r + 1] - h2[l] * p2[r - l + 1]) % M2 + M2) % M2;
    return {a, b};  // 兩個一起比才算相等
  }
};

減法之後那個 + M1) % M1 是必要的——C++ 的 % 對負數回傳負數，見 Modular-Arithmetic。

雜湊會被打爆，而且不是理論上而已

mod 2⁶⁴ 自然溢位（unsigned long long 不取模）是最危險的偷懶做法。 Thue-Morse 字串能構造出必然碰撞的反例，實測：

模數太小則會敗給生日悖論。 20000 個長度 10 的隨機字串：

同一組 Thue-Morse 串（長度 4096）對 mod 10⁹+7 沒有碰撞——質數模數擋掉了這個構造。

怎麼選

常見陷阱

Related Problems

• 0028-Find-the-Index-of-the-First-Occurrence-in-a-String — KMP 的原題
• 0459-Repeated-Substring-Pattern — n % (n - pi[n-1]) == 0 一行解
• 0214-Shortest-Palindrome — KMP 在 s + '#' + reverse(s) 上的經典技巧
• 1044-Longest-Duplicate-Substring — 雜湊 + 二分長度
• 0005-Longest-Palindromic-Substring — Manacher，或雜湊 + 二分
• Modular-Arithmetic — 雜湊的模運算基礎