字串演算法完全指南 — KMP、Rabin-Karp、Z-Algorithm 與 Aho-Corasick | 資料結構與演算法

// KMP 字串匹配演算法
// 預處理：O(m)，搜尋：O(n)，空間：O(m)

// 建構 Failure Function（部分匹配表）
// f[i] = 模式 p[0..i] 中最長「真前綴 = 真後綴」的長度
function buildFailure(pattern: string): number[] {
  const m = pattern.length;
  const f = new Array(m).fill(0);

  // k = 目前已知最長「真前綴 = 真後綴」的長度
  let k = 0;

  // 注意：從 i = 1 開始，f[0] 永遠是 0（單一字符無真前綴）
  for (let i = 1; i < m; i++) {
    // 不匹配時，利用已知的 f 值縮短 k（核心優化）
    while (k > 0 && pattern[k] !== pattern[i]) {
      k = f[k - 1]; // 回退到更短的匹配前綴
    }

    // 當前字符匹配，延伸長度
    if (pattern[k] === pattern[i]) {
      k++;
    }

    f[i] = k;
  }

  return f;
}

// KMP 搜尋：返回所有匹配的起始位置（0-indexed）
function kmpSearch(text: string, pattern: string): number[] {
  const n = text.length;
  const m = pattern.length;

  if (m === 0) return [0]; // 空模式特殊處理
  if (m > n) return [];

  const f = buildFailure(pattern);
  const results: number[] = [];
  let j = 0; // 模式指標（已匹配長度）

  for (let i = 0; i < n; i++) {
    // 不匹配時，模式指標利用 f 回退（文本指標 i 永遠不後退）
    while (j > 0 && text[i] !== pattern[j]) {
      j = f[j - 1];
    }

    // 當前字符匹配
    if (text[i] === pattern[j]) {
      j++;
    }

    // 完整匹配！記錄起始位置
    if (j === m) {
      results.push(i - m + 1);
      // 繼續搜尋下一個匹配（允許重疊匹配）
      j = f[j - 1];
    }
  }

  return results;
}

// ─── 使用範例 ──────────────────────────────────────────────────

// 基本匹配
console.log(kmpSearch("ABABDABABCABABD", "ABABCABAB"));
// 輸出：[5]（0-indexed）

// 重疊匹配
console.log(kmpSearch("AAAAAA", "AAA"));
// 輸出：[0, 1, 2, 3]（允許重疊）

// 無匹配
console.log(kmpSearch("ABCDEF", "XYZ"));
// 輸出：[]

// 判斷字串是否為重複子字串構成（LeetCode 459 變體）
function hasRepeatingUnit(s: string): boolean {
  const m = s.length;
  const f = buildFailure(s);
  const repeatLen = m - f[m - 1]; // 最短重複單元長度

  // 若 m 能被 repeatLen 整除，且 f[m-1] > 0，說明 s 是重複構成的
  return m % repeatLen === 0 && f[m - 1] > 0;
}

console.log(hasRepeatingUnit("abababab")); // 輸出：true（重複單元 "ab"）
console.log(hasRepeatingUnit("abcabcabc")); // 輸出：true（重複單元 "abc"）
console.log(hasRepeatingUnit("abcdef"));   // 輸出：false

// Rabin-Karp Rolling Hash 字串匹配
// 預處理：O(m)，搜尋：O(n) 平均，O(nm) 最差（碰撞時）
// 使用雙重雜湊降低碰撞機率

const RK_BASE = 31n;
const RK_MOD1 = 1_000_000_007n; // 第一個質數模
const RK_MOD2 = 998_244_353n;   // 第二個質數模（雙重雜湊）

interface RKHash {
  h1: bigint;
  h2: bigint;
}

// 計算字串區間 [start, end) 的雙重雜湊值
function computeHash(s: string, start: number, end: number): RKHash {
  let h1 = 0n, h2 = 0n;
  for (let i = start; i < end; i++) {
    const c = BigInt(s.charCodeAt(i) - 96); // 'a' → 1, 'b' → 2, ...
    h1 = (h1 * RK_BASE + c) % RK_MOD1;
    h2 = (h2 * RK_BASE + c) % RK_MOD2;
  }
  return { h1, h2 };
}

// Rabin-Karp 搜尋（單一模式）
function rabinKarp(text: string, pattern: string): number[] {
  const n = text.length;
  const m = pattern.length;

  if (m === 0 || m > n) return [];

  // 預計算 BASE^m（用於滾動時移除最左字符）
  let pow1 = 1n, pow2 = 1n;
  for (let i = 0; i < m; i++) {
    pow1 = (pow1 * RK_BASE) % RK_MOD1;
    pow2 = (pow2 * RK_BASE) % RK_MOD2;
  }

  // 計算模式的雜湊值
  const patHash = computeHash(pattern, 0, m);
  // 計算文本第一個視窗的雜湊值
  let { h1, h2 } = computeHash(text, 0, m);

  const results: number[] = [];
  const charCode = (s: string, i: number) => BigInt(s.charCodeAt(i) - 96);

  for (let i = 0; i <= n - m; i++) {
    // 雙重雜湊都命中才進行字串比對（幾乎不會誤判）
    if (h1 === patHash.h1 && h2 === patHash.h2) {
      if (text.substring(i, i + m) === pattern) {
        results.push(i);
      }
    }

    // 滾動更新：移除最左字符，加入右側新字符
    // 注意：必須加上 MOD 防止負數（關鍵陷阱！）
    if (i < n - m) {
      h1 = ((h1 * RK_BASE - charCode(text, i) * pow1 % RK_MOD1 + RK_MOD1)
            + charCode(text, i + m)) % RK_MOD1;
      h2 = ((h2 * RK_BASE - charCode(text, i) * pow2 % RK_MOD2 + RK_MOD2)
            + charCode(text, i + m)) % RK_MOD2;
    }
  }

  return results;
}

// ─── 使用範例 ──────────────────────────────────────────────────

console.log(rabinKarp("aababcabcabc", "abc"));
// 輸出：[3, 6, 9]

// Rabin-Karp 的獨特優勢：多模式等長匹配
function multiPatternSearch(
  text: string,
  patterns: string[]
): Map<string, number[]> {
  if (patterns.length === 0) return new Map();

  const m = patterns[0].length; // 假設所有模式等長
  const n = text.length;

  // 建立模式雜湊集合（O(總模式長度)）
  const patternHashes = new Map<string, string>();
  for (const pat of patterns) {
    if (pat.length !== m) continue;
    const { h1, h2 } = computeHash(pat, 0, m);
    patternHashes.set(`${h1},${h2}`, pat);
  }

  const results = new Map<string, number[]>();
  for (const pat of patterns) results.set(pat, []);

  if (n < m) return results;

  // 預計算 BASE^m
  let pow1 = 1n, pow2 = 1n;
  for (let i = 0; i < m; i++) {
    pow1 = (pow1 * RK_BASE) % RK_MOD1;
    pow2 = (pow2 * RK_BASE) % RK_MOD2;
  }

  let { h1, h2 } = computeHash(text, 0, m);
  const charCode = (i: number) => BigInt(text.charCodeAt(i) - 96);

  for (let i = 0; i <= n - m; i++) {
    const key = `${h1},${h2}`;
    if (patternHashes.has(key)) {
      const pat = patternHashes.get(key)!;
      if (text.substring(i, i + m) === pat) {
        results.get(pat)!.push(i);
      }
    }

    if (i < n - m) {
      h1 = ((h1 * RK_BASE - charCode(i) * pow1 % RK_MOD1 + RK_MOD1)
            + charCode(i + m)) % RK_MOD1;
      h2 = ((h2 * RK_BASE - charCode(i) * pow2 % RK_MOD2 + RK_MOD2)
            + charCode(i + m)) % RK_MOD2;
    }
  }

  return results;
}

// 多模式匹配範例
const multi = multiPatternSearch("thequickbrownfoxjumps", ["qui", "bro", "fox"]);
multi.forEach((positions, pat) => console.log(`"${pat}": [${positions}]`));
// 輸出：
// "qui": [3]
// "bro": [8]
// "fox": [13]

// Z-Algorithm：計算字串每個位置的 Z 陣列
// 時間：O(n)，空間：O(n)
// Z[i] = s[i..] 與 s[0..] 的最長公共前綴長度

function buildZArray(s: string): number[] {
  const n = s.length;
  const z = new Array(n).fill(0);
  z[0] = n; // 慣例：Z[0] = 字串長度本身

  // Z-Box [l, r]：目前已知的「延伸最遠的匹配區間」
  let l = 0, r = 0;

  for (let i = 1; i < n; i++) {
    if (i < r) {
      // i 在 Z-Box 內：利用已知的 Z[i-l] 初始化 Z[i]
      // 取 min 確保不超出 Z-Box 範圍（關鍵！）
      z[i] = Math.min(r - i, z[i - l]);
    }

    // 從 z[i] 已知的長度開始，繼續暴力延伸
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
      z[i]++;
    }

    // 若 i + z[i] 超過當前 r，更新 Z-Box
    if (i + z[i] > r) {
      l = i;
      r = i + z[i];
    }
  }

  return z;
}

// 使用 Z-Algorithm 進行字串搜尋
// 技巧：拼接 pattern + '$' + text，Z 值等於 pattern 長度的位置就是匹配點
function zSearch(text: string, pattern: string): number[] {
  const m = pattern.length;
  const combined = pattern + '$' + text; // '$' 確保不跨越邊界
  const z = buildZArray(combined);

  const results: number[] = [];
  const offset = m + 1; // text 在 combined 中的起始偏移

  for (let i = offset; i < combined.length; i++) {
    if (z[i] === m) {
      // Z 值等於 pattern 長度，表示完全匹配
      results.push(i - offset); // 轉換回 text 中的索引
    }
  }

  return results;
}

// ─── 使用範例 ──────────────────────────────────────────────────

console.log(zSearch("ABABDABABCABABD", "ABABCABAB"));
// 輸出：[5]

// Z-Algorithm 應用：找最短循環節（LeetCode 459）
function shortestRepeatingUnit(s: string): string {
  const n = s.length;
  const z = buildZArray(s);

  for (let len = 1; len <= n / 2; len++) {
    // 若長度 len 能整除 n，且 Z[len] + len >= n
    // 說明 s 是長度 len 的子字串重複而成
    if (n % len === 0 && z[len] + len >= n) {
      return s.substring(0, len);
    }
  }

  return s; // 無重複單元，整個 s 就是最短循環節
}

console.log(shortestRepeatingUnit("abababab")); // 輸出："ab"
console.log(shortestRepeatingUnit("abcabcabc")); // 輸出："abc"
console.log(shortestRepeatingUnit("abcdef")); // 輸出："abcdef"

// Aho-Corasick 多模式匹配自動機
// 建構：O(Σ|pi|)，搜尋：O(n + 匹配數)
// 其中 Σ|pi| 為所有模式的總長度

class AhoCorasick {
  private goto: Map<string, number>[]; // 轉移函式：goto[node][char] = nextNode
  private fail: number[];              // 失敗連結
  private output: number[][];          // 輸出列表：output[node] = [patternIdx, ...]
  private nodeCount: number;

  constructor() {
    // 初始化根節點（編號 0）
    this.goto = [new Map()];
    this.fail = [0];
    this.output = [[]];
    this.nodeCount = 1;
  }

  // 插入模式字串到 Trie 中
  // patternIdx：模式在模式列表中的索引
  insert(pattern: string, patternIdx: number): void {
    let cur = 0;

    for (const ch of pattern) {
      if (!this.goto[cur].has(ch)) {
        // 建立新節點
        const newNode = this.nodeCount++;
        this.goto.push(new Map());
        this.fail.push(0);
        this.output.push([]);
        this.goto[cur].set(ch, newNode);
      }
      cur = this.goto[cur].get(ch)!;
    }

    // 標記此節點為模式的結尾
    this.output[cur].push(patternIdx);
  }

  // BFS 建立失敗連結（類似 KMP 的 Failure Function）
  build(): void {
    const queue: number[] = [];

    // 根節點的所有直接子節點的失敗連結指向根
    for (const [, child] of this.goto[0]) {
      this.fail[child] = 0;
      queue.push(child);
    }

    // BFS 遍歷建立所有節點的失敗連結
    let head = 0;
    while (head < queue.length) {
      const u = queue[head++];

      for (const [ch, v] of this.goto[u]) {
        // 計算子節點 v 的失敗連結
        let f = this.fail[u];
        while (f !== 0 && !this.goto[f].has(ch)) {
          f = this.fail[f]; // 沿失敗連結回溯
        }
        this.fail[v] = this.goto[f].has(ch) ? this.goto[f].get(ch)! : 0;

        // 如果失敗連結指向根的 ch 子節點就是 v 自己，則指向根
        if (this.fail[v] === v) this.fail[v] = 0;

        // 合併輸出連結：繼承失敗連結的輸出
        this.output[v] = [
          ...this.output[v],
          ...this.output[this.fail[v]]
        ];

        queue.push(v);
      }
    }
  }

  // 搜尋文本，返回所有匹配結果
  search(
    text: string,
    patterns: string[]
  ): Array<{ pattern: string; position: number }> {
    const results: Array<{ pattern: string; position: number }> = [];
    let cur = 0;

    for (let i = 0; i < text.length; i++) {
      const ch = text[i];

      // 沿失敗連結回溯，直到找到有 ch 轉移的節點或回到根
      while (cur !== 0 && !this.goto[cur].has(ch)) {
        cur = this.fail[cur];
      }
      cur = this.goto[cur].has(ch) ? this.goto[cur].get(ch)! : 0;

      // 收集此節點上的所有匹配模式
      for (const patIdx of this.output[cur]) {
        results.push({
          pattern: patterns[patIdx],
          position: i - patterns[patIdx].length + 1
        });
      }
    }

    return results;
  }
}

// ─── 使用範例 ──────────────────────────────────────────────────

const ac = new AhoCorasick();
const patterns = ["he", "she", "his", "hers"];

// 插入所有模式
patterns.forEach((pat, idx) => ac.insert(pat, idx));

// 建立失敗連結
ac.build();

// 搜尋文本
const matches = ac.search("ahishers", patterns);
matches.forEach(({ pattern, position }) => {
  console.log(`"${pattern}" 在位置 ${position}`);
});
// 輸出：
// "his" 在位置 1
// "he" 在位置 4
// "she" 在位置 3
// "hers" 在位置 4

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

// ===== KMP 演算法 =====
// 預處理 O(m)，搜尋 O(n)，空間 O(m)

// 建構 Failure Function
vector<int> buildFailure(const string& pattern) {
    int m = pattern.size();
    vector<int> f(m, 0);
    int k = 0;

    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern[k] != pattern[i]) {
            k = f[k - 1]; // 回退到更短的前綴
        }
        if (pattern[k] == pattern[i]) k++;
        f[i] = k;
    }
    return f;
}

// KMP 搜尋，返回所有匹配起始位置（0-indexed）
vector<int> kmpSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m == 0 || m > n) return {};

    auto f = buildFailure(pattern);
    vector<int> results;
    int j = 0;

    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = f[j - 1];
        }
        if (text[i] == pattern[j]) j++;
        if (j == m) {
            results.push_back(i - m + 1);
            j = f[j - 1]; // 繼續搜尋重疊匹配
        }
    }

    return results;
}

// ===== Z-Algorithm =====
// 時間 O(n)，空間 O(n)

vector<int> buildZArray(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    z[0] = n;
    int l = 0, r = 0;

    for (int i = 1; i < n; i++) {
        if (i < r) {
            z[i] = min(r - i, z[i - l]); // 取 min 避免超出 Z-Box
        }
        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-Algorithm 搜尋字串
vector<int> zSearch(const string& text, const string& pattern) {
    string combined = pattern + "$" + text;
    int m = pattern.size();
    auto z = buildZArray(combined);

    vector<int> results;
    int offset = m + 1;
    for (int i = offset; i < (int)combined.size(); i++) {
        if (z[i] == m) {
            results.push_back(i - offset);
        }
    }
    return results;
}

// ===== Aho-Corasick 自動機 =====
// 建構 O(Σ|pi|)，搜尋 O(n + 匹配數)

struct AhoCorasick {
    static const int ALPHA = 26;
    vector<array<int, ALPHA>> go;  // 轉移函式
    vector<int> fail;              // 失敗連結
    vector<vector<int>> output;    // 輸出列表

    AhoCorasick() {
        go.push_back({});
        go[0].fill(-1);
        fail.push_back(0);
        output.push_back({});
    }

    // 插入模式字串
    void insert(const string& pattern, int patIdx) {
        int cur = 0;
        for (char ch : pattern) {
            int c = ch - 'a';
            if (go[cur][c] == -1) {
                go[cur][c] = go.size();
                go.push_back({});
                go.back().fill(-1);
                fail.push_back(0);
                output.push_back({});
            }
            cur = go[cur][c];
        }
        output[cur].push_back(patIdx);
    }

    // BFS 建立失敗連結
    void build() {
        queue<int> q;
        // 根的直接子節點：失敗連結指向根
        for (int c = 0; c < ALPHA; c++) {
            if (go[0][c] == -1) {
                go[0][c] = 0; // 無對應子節點時指回根
            } else {
                fail[go[0][c]] = 0;
                q.push(go[0][c]);
            }
        }

        while (!q.empty()) {
            int u = q.front(); q.pop();

            for (int c = 0; c < ALPHA; c++) {
                if (go[u][c] == -1) {
                    // 無子節點：直接跳到失敗連結的對應子節點
                    go[u][c] = go[fail[u]][c];
                } else {
                    int v = go[u][c];
                    fail[v] = go[fail[u]][c];
                    // 合併輸出：繼承失敗連結的輸出
                    for (int idx : output[fail[v]]) {
                        output[v].push_back(idx);
                    }
                    q.push(v);
                }
            }
        }
    }

    // 搜尋文本
    vector<pair<int, int>> search(
        const string& text,
        const vector<string>& patterns
    ) {
        vector<pair<int, int>> results; // {模式索引, 起始位置}
        int cur = 0;

        for (int i = 0; i < (int)text.size(); i++) {
            cur = go[cur][text[i] - 'a'];

            for (int patIdx : output[cur]) {
                int startPos = i - (int)patterns[patIdx].size() + 1;
                results.push_back({patIdx, startPos});
            }
        }

        return results;
    }
};

// ===== 主測試函式 =====

int main() {
    // KMP 測試
    {
        auto results = kmpSearch("ABABDABABCABABD", "ABABCABAB");
        cout << "KMP 匹配位置: ";
        for (int pos : results) cout << pos << " ";
        cout << "\n"; // 輸出：5
    }

    // Z-Algorithm 測試
    {
        auto results = zSearch("ABABDABABCABABD", "ABABCABAB");
        cout << "Z-Search 匹配位置: ";
        for (int pos : results) cout << pos << " ";
        cout << "\n"; // 輸出：5
    }

    // Aho-Corasick 測試
    {
        AhoCorasick ac;
        vector<string> patterns = {"he", "she", "his", "hers"};
        for (int i = 0; i < (int)patterns.size(); i++) {
            ac.insert(patterns[i], i);
        }
        ac.build();

        string text = "ahishers";
        auto matches = ac.search(text, patterns);
        cout << "Aho-Corasick 匹配：\n";
        for (auto [patIdx, startPos] : matches) {
            cout << "  \"" << patterns[patIdx]
                 << "\" 在位置 " << startPos << "\n";
        }
    }

    return 0;
}

// 陷阱 1：KMP Failure Function 的起始索引
// 錯誤：從 i = 0 開始，f[0] 會被錯誤設為 1
function badFailure(pattern: string): number[] {
  const f = new Array(pattern.length).fill(0);
  let k = 0;
  for (let i = 0; i < pattern.length; i++) { // ← 從 0 開始是錯的！
    while (k > 0 && pattern[k] !== pattern[i]) k = f[k - 1];
    if (pattern[k] === pattern[i]) k++;
    f[i] = k; // f[0] = 1，但定義上應為 0
  }
  return f;
}

// 正確：從 i = 1 開始，f[0] = 0（定義：長度 1 的字串無真前綴）
function goodFailure(pattern: string): number[] {
  const f = new Array(pattern.length).fill(0);
  let k = 0;
  for (let i = 1; i < pattern.length; i++) { // ← 從 1 開始
    while (k > 0 && pattern[k] !== pattern[i]) k = f[k - 1];
    if (pattern[k] === pattern[i]) k++;
    f[i] = k;
  }
  return f;
}

// 陷阱 2：Rabin-Karp 滾動更新時的模負數
// 錯誤：直接相減，結果可能為負數
h1 = (h1 * BASE - remove * pow) % MOD; // ← 可能為負！

// 正確：先加 MOD 再取餘，確保結果非負
h1 = ((h1 * BASE - remove * pow % MOD + MOD) + add) % MOD;

// 陷阱 3：Z-Algorithm 不取 min 導致越界
// 錯誤：直接使用 z[i-l]，可能超出 Z-Box 範圍
z[i] = z[i - l]; // ← 超出 [l, r] 範圍時會錯

// 正確：取 min(r - i, z[i - l]) 確保不超出
z[i] = Math.min(r - i, z[i - l]);

// LeetCode 28 — Find the Index of the First Occurrence in a String
function strStr(haystack: string, needle: string): number {
  const n = haystack.length;
  const m = needle.length;

  if (m === 0) return 0;
  if (m > n) return -1;

  // 建構 Failure Function
  const f = new Array(m).fill(0);
  let k = 0;
  for (let i = 1; i < m; i++) {
    while (k > 0 && needle[k] !== needle[i]) k = f[k - 1];
    if (needle[k] === needle[i]) k++;
    f[i] = k;
  }

  // KMP 搜尋：找到第一個匹配立即返回
  let j = 0;
  for (let i = 0; i < n; i++) {
    while (j > 0 && haystack[i] !== needle[j]) j = f[j - 1];
    if (haystack[i] === needle[j]) j++;
    if (j === m) return i - m + 1;
  }

  return -1;
}

console.log(strStr("sadbutsad", "sad")); // 輸出：0
console.log(strStr("leetcode", "leeto")); // 輸出：-1

// LeetCode 214 — Shortest Palindrome
// 時間：O(n)，空間：O(n)
function shortestPalindrome(s: string): string {
  const n = s.length;
  if (n <= 1) return s;

  // 拼接 s + '#' + reverse(s)
  // '#' 防止 Failure Function 跨越邊界
  const rev = s.split('').reverse().join('');
  const combined = s + '#' + rev;
  const total = combined.length;

  // 計算 KMP Failure Function
  const f = new Array(total).fill(0);
  let k = 0;
  for (let i = 1; i < total; i++) {
    while (k > 0 && combined[k] !== combined[i]) k = f[k - 1];
    if (combined[k] === combined[i]) k++;
    f[i] = k;
  }

  // f[total-1] = 最長回文前綴的長度
  // 在 s 前面補上 rev 中前 (n - f[total-1]) 個字符
  const longestPalPrefixLen = f[total - 1];
  const prefix = rev.substring(0, n - longestPalPrefixLen);

  return prefix + s;
}

console.log(shortestPalindrome("aacecaaa")); // 輸出："aaacecaaa"
console.log(shortestPalindrome("abcd"));     // 輸出："dcbabcd"

// LeetCode 1392 — Longest Happy Prefix
// 時間：O(n)，空間：O(n)
function longestPrefix(s: string): string {
  const n = s.length;

  // 建構 Failure Function
  const f = new Array(n).fill(0);
  let k = 0;
  for (let i = 1; i < n; i++) {
    while (k > 0 && s[k] !== s[i]) k = f[k - 1];
    if (s[k] === s[i]) k++;
    f[i] = k;
  }

  // f[n-1] 即為最長「真前綴 = 真後綴」的長度
  return s.substring(0, f[n - 1]);
}

console.log(longestPrefix("level"));        // 輸出："l"
console.log(longestPrefix("ababab"));       // 輸出："abab"
console.log(longestPrefix("leetcodeleet")); // 輸出："leet"