KMP 法 (Knuth-Morris-Pratt Algorithm)
(string/str_007_kmp.cpp)

• View this file on GitHub
• Last update: 2020-01-11 16:10:37+09:00
• Link: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

Code

// @brief KMP 法 (Knuth-Morris-Pratt Algorithm)
template <typename Tp>
struct KMP {
    Tp p; int len;
    vector<int> fail;
    KMP() {}
    KMP(Tp p_) : p(p_), len(p_.size()) {
        // @brief 文字列 $p[0:i-1]$ の接頭辞と接尾辞は最大何文字一致する？ (ただし、$|p[0:i-1]|$ 文字未満のみ考慮)
        // @brief MP 法に比べ、失敗時の遷移が log 回に改善されている
        // @see http://www-igm.univ-mlv.fr/~lecroq/string/node8.html
        fail.resize(len + 1, -1);
        for(int i=0, j=-1; i<len; i++) {
            // その時点で一致しなければ fail[j] 文字以下の一致となる
            // j を fail[j] に変更
            while(j >= 0 and p[j] != p[i]) j = fail[j];
            j++;
            fail[i+1] = (i+1 < len and p[i+1] == p[j] ? fail[j] : j);
        }
    }

    // @brief 文字列 $s$ における $p$ の出現位置 (開始位置) のリスト
    vector<int> match(Tp s) {
        int N = s.size();
        vector<int> occur;
        for(int i=0, k=0; i<N; i++) {
            while(k >= 0 and s[i] != p[k]) k = fail[k];
            if(++k == len) {
                occur.push_back(i-len+1);
                k = fail[k];
            }
        }
        return occur;
    }
};

#line 1 "string/str_007_kmp.cpp"
// @brief KMP 法 (Knuth-Morris-Pratt Algorithm)
template <typename Tp>
struct KMP {
    Tp p; int len;
    vector<int> fail;
    KMP() {}
    KMP(Tp p_) : p(p_), len(p_.size()) {
        // @brief 文字列 $p[0:i-1]$ の接頭辞と接尾辞は最大何文字一致する？ (ただし、$|p[0:i-1]|$ 文字未満のみ考慮)
        // @brief MP 法に比べ、失敗時の遷移が log 回に改善されている
        // @see http://www-igm.univ-mlv.fr/~lecroq/string/node8.html
        fail.resize(len + 1, -1);
        for(int i=0, j=-1; i<len; i++) {
            // その時点で一致しなければ fail[j] 文字以下の一致となる
            // j を fail[j] に変更
            while(j >= 0 and p[j] != p[i]) j = fail[j];
            j++;
            fail[i+1] = (i+1 < len and p[i+1] == p[j] ? fail[j] : j);
        }
    }

    // @brief 文字列 $s$ における $p$ の出現位置 (開始位置) のリスト
    vector<int> match(Tp s) {
        int N = s.size();
        vector<int> occur;
        for(int i=0, k=0; i<N; i++) {
            while(k >= 0 and s[i] != p[k]) k = fail[k];
            if(++k == len) {
                occur.push_back(i-len+1);
                k = fail[k];
            }
        }
        return occur;
    }
};

Back to top page