KMP法
(string/kmp.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

概要

Knuth-Morris-Pratt 法。 文字列 pattern の失敗関数テーブルを kmp_table で構築し、 kmp_search(text, pattern) で pattern の出現開始位置を列挙する。

計算量

• kmp_table(s) : $O(

  s

  )$

• kmp_search(text, pattern) : $O(

  text

  +

  pattern

  )$

使い方

1. auto pos = kmp_search(text, pattern);
2. pos に一致開始位置（0-indexed）が昇順で入る

実装上の補足

• pattern が空文字列のときは、0..|text| のすべてを返す。

Verified with

• test/aoj_alds1_14_b.test.cpp

Code

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

vector<int> kmp_search(const string &text, const string &pattern){
    int n = text.size(), m = pattern.size();
    vector<int> res;
    if(pattern.empty()){
        res.resize(n + 1);
        iota(res.begin(), res.end(), 0);
        return res;
    }
    auto table = kmp_table(pattern);
    for (int i = 0, j = 0; i < n;) {
        while(j >= 0 && text[i] != pattern[j]) j = table[j];
        i++, j++;
        if(j == m){
            res.emplace_back(i - j);
            j = table[j];
        }
    }
    return res;
}

/**
 * @brief KMP法
 */

#line 1 "string/kmp.cpp"
vector<int> kmp_table(const string &s){
    int n = s.size();
    vector<int> table(n + 1);
    table[0] = -1;
    for (int i = 0, j = -1; i < n;) {
        while(j >= 0 && s[i] != s[j]) j = table[j];
        i++, j++;
        table[i] = j;
    }
    return table;
}

vector<int> kmp_search(const string &text, const string &pattern){
    int n = text.size(), m = pattern.size();
    vector<int> res;
    if(pattern.empty()){
        res.resize(n + 1);
        iota(res.begin(), res.end(), 0);
        return res;
    }
    auto table = kmp_table(pattern);
    for (int i = 0, j = 0; i < n;) {
        while(j >= 0 && text[i] != pattern[j]) j = table[j];
        i++, j++;
        if(j == m){
            res.emplace_back(i - j);
            j = table[j];
        }
    }
    return res;
}

/**
 * @brief KMP法
 */

Back to top page