KMP 算法 TLE 優化：Next 陣列計算與匹配細節決定成敗

題目規模

• 測資組數 N ≤ 20
• 模式串長度 ≤ 10⁴
• 原串長度 ≤ 10⁶
• 總輸入可達 2×10⁷ 字符，O(N×M) 暴力解法必超時。

常見 TLE 原因

1. Next 陣列計算錯誤/未優化：標準 KMP 構建 next 時需利用已匹配前綴資訊，避免回溯。
2. 匹配階段指針回退邏輯錯誤：導致重複比較，退化為 O(N×M)。
3. 頻繁動態記憶體分配：每測資 malloc/free next 陣列，開銷大。

優化要點

1. Next 陣列正確構建（含優化值）

void buildNext(const char* pat, int* next) {
    int m = strlen(pat);
    next[0] = 0;
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pat[i] != pat[j]) j = next[j-1];
        if (pat[i] == pat[j]) j++;
        next[i] = j;
    }
    // 可選優化：若 pat[i+1] == pat[next[i]] 則 next[i] = next[next[i]-1]
}

2. 匹配主迴圈無回溯

int kmpSearch(const char* txt, const char* pat, int* next) {
    int n = strlen(txt), m = strlen(pat);
    int count = 0;
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && txt[i] != pat[j]) j = next[j-1];
        if (txt[i] == pat[j]) j++;
        if (j == m) {
            count++;
            j = next[j-1]; // 繼續尋找下一個匹配（允許重疊）
        }
    }
    return count;
}

3. 記憶體重用

在主函式分配最大可能的 next 陣列（10000+5），各測資重用，避免重複分配。

複雜度保證

構建 Next O(m)，匹配 O(n)，總計 O(n+m) 每測資，滿足 1000ms 限制。