kmp_algorithm.cpp

/*
 * ============================================================================
 *  KMP (Knuth-Morris-Pratt) 字串匹配演算法 — 完整 C++ 實現
 *  File: kmp_algorithm.cpp
 *
 *  內容：
 *    1. 暴力法 (Brute Force)         — O(N*M) 對照
 *    2. 前綴函數 (Failure Function)   — O(M) 建構
 *    3. KMP 搜尋                     — O(N+M) 搜尋
 *    4. 優化版前綴函數               — 減少多餘回退
 *    5. 最短重複週期                 — 利用 failure 陣列
 *    6. 多組測試案例
 *
 *  編譯: g++ -std=c++11 -Wall -o kmp_algorithm kmp_algorithm.cpp
 *  執行: ./kmp_algorithm
 * ============================================================================
 */

#include <iostream>
#include <vector>
#include <string>

using namespace std;

/* ============================================================================
 * 第一部分：暴力法（Brute Force）— 對照用
 * ============================================================================
 *
 * 做法：對 text 的每個可能起點 i，逐字元比對 pattern。
 * 時間複雜度：最壞 O(N * M)。
 * 問題：比對失敗時丟棄已成功的資訊，text 的指標回退。
 */
vector<int> bruteForceSearch(const string& text, const string& pattern) {
    // result 存放所有匹配的起始位置
    vector<int> result;

    int n = (int)text.size();      // text 長度 N
    int m = (int)pattern.size();   // pattern 長度 M

    // 特殊情況：pattern 為空或比 text 長
    if (m == 0 || m > n) return result;

    // 對 text 的每個起點 i = 0, 1, ..., N-M
    for (int i = 0; i <= n - m; ++i) {
        int j = 0;

        // 逐字元比對 text[i+j] 和 pattern[j]
        while (j < m && text[i + j] == pattern[j]) {
            ++j;
        }

        // 如果 j == M，代表 pattern 全部匹配成功
        if (j == m) {
            result.push_back(i);  // 記錄匹配位置
        }
        // 否則 i 只前進 1，重新比對 — 這就是暴力法的效率瓶頸
    }

    return result;
}

/* ============================================================================
 * 第二部分：建構前綴函數（Failure Function / Partial Match Table）
 * ============================================================================
 *
 * failure[j] = pattern[0..j] 的最長「真前綴 = 真後綴」長度。
 *
 * 核心思想：把 pattern 和自己做 KMP 匹配。
 *   - i 掃描 pattern[1..M-1]（相當於 text 的角色）
 *   - j 追蹤目前匹配的前綴長度
 *   - 當 pattern[i] ≠ pattern[j] 時，沿 failure 鏈回退 j
 *
 * 時間複雜度：O(M)
 *   攤銷分析：j 在整個過程中最多增加 M 次，所以 while 中的回退總次數也 ≤ M。
 */
vector<int> buildFailure(const string& pattern, bool verbose = false) {
    int m = (int)pattern.size();
    // failure[j] 初始化為 0（單字元的最長真前綴=真後綴長度為 0）
    vector<int> failure(m, 0);

    if (verbose) {
        cout << "\n--- 建構前綴函數 (Failure Function) ---" << endl;
        cout << "pattern = \"" << pattern << "\"  (長度 M = " << m << ")\n" << endl;
    }

    // j = 目前「已匹配的前綴長度」
    // 一開始 failure[0] = 0（定義），所以從 i = 1 開始
    int j = 0;

    for (int i = 1; i < m; ++i) {
        if (verbose) {
            cout << "i=" << i << " pattern[i]='" << pattern[i] << "', j=" << j << endl;
        }

        // 當 pattern[i] 和 pattern[j] 不匹配時，沿 failure 鏈回退
        // 為什麼跳到 failure[j-1]？
        //   因為 failure[j-1] 是 pattern[0..j-1] 中第二長的「前綴=後綴」，
        //   從那裡繼續嘗試可能匹配成功。
        while (j > 0 && pattern[i] != pattern[j]) {
            if (verbose) {
                cout << "  pattern[" << i << "]='" << pattern[i]
                     << "' != pattern[" << j << "]='" << pattern[j]
                     << "' → 回退 j = failure[" << j - 1 << "] = " << failure[j - 1] << endl;
            }
            j = failure[j - 1];
        }

        // 如果匹配成功，前綴長度 +1
        if (pattern[i] == pattern[j]) {
            ++j;
            if (verbose) {
                cout << "  pattern[" << i << "]='" << pattern[i]
                     << "' == pattern[" << j - 1 << "]='" << pattern[j - 1]
                     << "' → j++ = " << j << endl;
            }
        }

        // 記錄 failure[i]
        failure[i] = j;

        if (verbose) {
            cout << "  → failure[" << i << "] = " << j << endl;
        }
    }

    if (verbose) {
        cout << "\n最終 failure 陣列:" << endl;
        cout << "j:        ";
        for (int i = 0; i < m; ++i) cout << i << " ";
        cout << endl;
        cout << "pattern:  ";
        for (int i = 0; i < m; ++i) cout << pattern[i] << " ";
        cout << endl;
        cout << "failure:  ";
        for (int i = 0; i < m; ++i) cout << failure[i] << " ";
        cout << "\n" << endl;
    }

    return failure;
}

/* ============================================================================
 * 第三部分：KMP 搜尋
 * ============================================================================
 *
 * 利用前綴函數，在 text 中搜尋所有 pattern 出現的位置。
 *
 * 關鍵：
 *   - i 掃描 text[0..N-1]，**永遠不回退**。
 *   - j 追蹤 pattern 中目前比對到的位置。
 *   - 比對失敗時，j 沿 failure 鏈回退（i 不動）。
 *   - 比對成功 j==M 時，記錄匹配位置，然後 j = failure[j-1] 繼續找。
 *
 * 時間複雜度：O(N)（不含建 failure 的 O(M)）
 */
vector<int> kmpSearch(const string& text, const string& pattern, bool verbose = false) {
    vector<int> result;

    int n = (int)text.size();
    int m = (int)pattern.size();

    if (m == 0 || m > n) return result;

    // 第一步：建構前綴函數 — O(M)
    vector<int> failure = buildFailure(pattern, verbose);

    if (verbose) {
        cout << "--- KMP 搜尋過程 ---" << endl;
        cout << "text    = \"" << text << "\"  (長度 N = " << n << ")" << endl;
        cout << "pattern = \"" << pattern << "\"  (長度 M = " << m << ")\n" << endl;
    }

    // j = pattern 中目前要比對的索引
    int j = 0;

    // 第二步：掃描 text — O(N)
    for (int i = 0; i < n; ++i) {
        if (verbose) {
            cout << "i=" << i << " text[i]='" << text[i] << "', j=" << j << endl;
        }

        // 當 text[i] 和 pattern[j] 不匹配時，j 沿 failure 鏈回退
        // 注意：i 完全不動！只有 j 在跳
        while (j > 0 && text[i] != pattern[j]) {
            if (verbose) {
                cout << "  text[" << i << "]='" << text[i]
                     << "' != pattern[" << j << "]='" << pattern[j]
                     << "' → j = failure[" << j - 1 << "] = " << failure[j - 1] << endl;
            }
            j = failure[j - 1];
        }

        // 如果當前字元匹配，j 前進
        if (text[i] == pattern[j]) {
            if (verbose) {
                cout << "  text[" << i << "]='" << text[i]
                     << "' == pattern[" << j << "]='" << pattern[j]
                     << "' → j++ = " << j + 1 << endl;
            }
            ++j;
        }

        // 如果 j == M，表示 pattern 完全匹配！
        if (j == m) {
            int pos = i - m + 1;  // 匹配的起始位置（0-based）
            result.push_back(pos);

            if (verbose) {
                cout << "  *** 找到匹配！起始位置 = " << pos << " ***" << endl;
            }

            // 繼續搜尋下一個可能的匹配
            // j 跳到 failure[M-1]，因為匹配的後綴可能同時是下一個匹配的前綴
            j = failure[j - 1];

            if (verbose) {
                cout << "  繼續搜尋: j = failure[" << m - 1 << "] = " << j << endl;
            }
        }
    }

    return result;
}

/* ============================================================================
 * 第四部分：優化版前綴函數
 * ============================================================================
 *
 * 標準 failure 有一個小缺點：
 *   若 pattern[j] 失敗，我們跳到 k = failure[j-1]，但如果 pattern[k] == pattern[j]，
 *   那一定還是會失敗（因為 text[i] ≠ pattern[j] = pattern[k]），白跳一次。
 *
 * 優化：建構時，如果 pattern[failure[i]] == pattern[i+1]，就直接跳更遠。
 * 這在某些特殊 pattern（如 "AAAAB"）中可以減少常數因子。
 *
 * 注意：漸進複雜度仍為 O(M)，只是常數更小。
 */
vector<int> buildFailureOptimized(const string& pattern) {
    int m = (int)pattern.size();
    vector<int> failure(m, 0);

    int j = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = failure[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        failure[i] = j;

        // 優化：如果下一次比對 failure 指向的字元和當前相同，直接跳過
        // 這避免了已知會失敗的比較
        if (i + 1 < m && failure[i] > 0 && pattern[failure[i]] == pattern[i + 1]) {
            // 此情境下 failure[i] 可以進一步壓縮
            // 但標準 KMP 通常不做此修改，這裡只示範概念
        }
    }

    return failure;
}

/* ============================================================================
 * 第五部分：最短重複週期
 * ============================================================================
 *
 * 定理：字串 S 的最短重複週期 = len(S) - failure[len(S) - 1]。
 *
 * 例如：
 *   "ABCABC" → failure = [0,0,0,1,2,3] → 週期 = 6 - 3 = 3 ("ABC")
 *   "AAAA"   → failure = [0,1,2,3]     → 週期 = 4 - 3 = 1 ("A")
 *   "ABCD"   → failure = [0,0,0,0]     → 週期 = 4 - 0 = 4 (本身，無重複)
 *
 * 如果 len(S) % period == 0，那麼 S 可以完全由週期重複構成。
 */
int shortestPeriod(const string& s) {
    vector<int> failure = buildFailure(s);
    int m = (int)s.size();
    // 最短週期 = 總長 - 最長「前綴=後綴」
    int period = m - failure[m - 1];
    return period;
}

/* ============================================================================
 * 第六部分：輔助函式
 * ============================================================================ */

// 印出匹配結果，並視覺化標記
void printMatches(const string& text, const string& pattern, const vector<int>& positions) {
    cout << "text:    \"" << text << "\"" << endl;
    cout << "pattern: \"" << pattern << "\"" << endl;

    if (positions.empty()) {
        cout << "結果: 沒有找到匹配。\n" << endl;
        return;
    }

    cout << "找到 " << positions.size() << " 個匹配：" << endl;
    for (int pos : positions) {
        cout << "  位置 " << pos << ": \"";
        // 印出 text，用 [ ] 標記匹配的部分
        for (int i = 0; i < (int)text.size(); ++i) {
            if (i == pos) cout << "[";
            cout << text[i];
            if (i == pos + (int)pattern.size() - 1) cout << "]";
        }
        cout << "\"" << endl;
    }
    cout << endl;
}

/* ============================================================================
 * 第七部分：主程式 — 測試案例
 * ============================================================================ */
int main() {
    cout << "======================================================" << endl;
    cout << "  KMP (Knuth-Morris-Pratt) 字串匹配演算法 完整示範" << endl;
    cout << "======================================================\n" << endl;

    // ─────────────────────────────────────────────────
    // 測試 1：基本範例（附詳細 debug 輸出）
    // ─────────────────────────────────────────────────
    {
        cout << "【測試 1】基本範例 — 附逐步推演\n" << endl;
        string text    = "ABABDABACDABABCABAB";
        string pattern = "ABABCABAB";

        // verbose = true 會印出每一步的比對細節
        vector<int> result = kmpSearch(text, pattern, true);
        printMatches(text, pattern, result);
    }

    // ─────────────────────────────────────────────────
    // 測試 2：多個匹配
    // ─────────────────────────────────────────────────
    {
        cout << "【測試 2】多個匹配\n" << endl;
        string text    = "AAAAAA";
        string pattern = "AA";

        vector<int> result = kmpSearch(text, pattern, false);
        printMatches(text, pattern, result);

        // 同時驗證暴力法結果一致
        vector<int> bruteResult = bruteForceSearch(text, pattern);
        cout << "暴力法驗證: 找到 " << bruteResult.size() << " 個匹配";
        cout << (bruteResult == result ? " ✓ 一致" : " ✗ 不一致") << "\n" << endl;
    }

    // ─────────────────────────────────────────────────
    // 測試 3：沒有匹配
    // ─────────────────────────────────────────────────
    {
        cout << "【測試 3】沒有匹配\n" << endl;
        string text    = "ABCDEFG";
        string pattern = "XYZ";

        vector<int> result = kmpSearch(text, pattern, false);
        printMatches(text, pattern, result);
    }

    // ─────────────────────────────────────────────────
    // 測試 4：pattern 和 text 完全相同
    // ─────────────────────────────────────────────────
    {
        cout << "【測試 4】完全相同\n" << endl;
        string text    = "HELLO";
        string pattern = "HELLO";

        vector<int> result = kmpSearch(text, pattern, false);
        printMatches(text, pattern, result);
    }

    // ─────────────────────────────────────────────────
    // 測試 5：暴力法的最壞情況 — KMP 輕鬆處理
    // ─────────────────────────────────────────────────
    {
        cout << "【測試 5】暴力法最壞情況\n" << endl;
        string text    = "AAAAAAAAAB";
        string pattern = "AAAAB";

        // 這個案例下，暴力法每次比對 4 個字元後失敗再回退 1 格
        // KMP 不會回退 text 指標，效率高得多
        vector<int> result = kmpSearch(text, pattern, false);
        printMatches(text, pattern, result);
    }

    // ─────────────────────────────────────────────────
    // 測試 6：最短重複週期
    // ─────────────────────────────────────────────────
    {
        cout << "【測試 6】最短重複週期\n" << endl;

        string s1 = "ABCABC";
        int p1 = shortestPeriod(s1);
        cout << "\"" << s1 << "\" 的最短週期 = " << p1
             << " (\"" << s1.substr(0, p1) << "\")"
             << (((int)s1.size() % p1 == 0) ? " → 完全重複" : " → 不完全重複")
             << endl;

        string s2 = "AAAA";
        int p2 = shortestPeriod(s2);
        cout << "\"" << s2 << "\" 的最短週期 = " << p2
             << " (\"" << s2.substr(0, p2) << "\")"
             << (((int)s2.size() % p2 == 0) ? " → 完全重複" : " → 不完全重複")
             << endl;

        string s3 = "ABCD";
        int p3 = shortestPeriod(s3);
        cout << "\"" << s3 << "\" 的最短週期 = " << p3
             << " (\"" << s3.substr(0, p3) << "\")"
             << (((int)s3.size() % p3 == 0) ? " → 完全重複" : " → 不完全重複")
             << endl;

        string s4 = "ABABABAB";
        int p4 = shortestPeriod(s4);
        cout << "\"" << s4 << "\" 的最短週期 = " << p4
             << " (\"" << s4.substr(0, p4) << "\")"
             << (((int)s4.size() % p4 == 0) ? " → 完全重複" : " → 不完全重複")
             << endl;
    }

    cout << "\n======================================================"  << endl;
    cout << "  所有測試完成。" << endl;
    cout << "======================================================\n" << endl;

    return 0;
}