Knuth-Morris-Pratt Algorithm
(string/kmp.hpp)

• View this file on GitHub
• Last update: 2024-01-07 22:05:53+09:00
• Include: #include "string/kmp.hpp"

Description

Knuth-Morris-Pratt のアルゴリズムは，文字列中のパターンの出現位置を列挙するアルゴリズムである．

パターンの prefix function (P[:i+1] の接尾辞でもある最長の proper prefix) を各$i$について前計算することで， 文字の比較の回数を減らしている．

Operations

• vector<int> prefix_function(vector<T> s)
• vector<int> prefix_function(string s)
  • 数列 s の prefix function を計算する
  • 時間計算量: $O(n)$
• vector<int> kmp(vector<T> txt, vector<T> pat, vector<int> pf)
• vector<int> kmp(string txt, string pat, vector<int> pf)
  • txt中のpatの出現位置を列挙する
  • 時間計算量: $O(n + m)$
• vector<vector<pair<int, bool>>> matching_automaton(string s)
  • s のマッチングオートマトンを返す．ret[i][c] は，$i$ 文字マッチしているときに文字 c が出現したときの遷移先と，全体がマッチしたか否かを返す．
  • 時間計算量: $O(nA)$, $A$ はアルファベットサイズ

Reference

• KMP Algorithm for Pattern Searching

Required by

• 2D Pattern Search (Baker-Bird Algorithm) (string/pattern_search_2d.hpp)

Verified with

• test/aoj/ALDS1_14_B.kmp.test.cpp
• test/aoj/ALDS1_14_C.test.cpp

Code

#pragma once
#include <string>
#include <vector>

template <typename T>
std::vector<int> prefix_function(const std::vector<T>& s) {
    const int n = s.size();
    std::vector<int> ret(n);
    for (int len = 0, i = 1; i < n; ++i) {
        if (s[i] == s[len]) {
            ++len;
            ret[i] = len;
        } else {
            if (len != 0) {
                len = ret[len - 1];
                --i;
            } else {
                ret[i] = 0;
            }
        }
    }
    return ret;
}

template <typename T>
std::vector<int> kmp(const std::vector<T>& txt, const std::vector<T>& pat,
                     const std::vector<int>& pf) {
    const int n = txt.size(), m = pat.size();
    std::vector<int> match;
    for (int i = 0, j = 0; i < n;) {
        if (pat[j] == txt[i]) {
            ++i;
            ++j;
        }
        if (j == m) {
            match.push_back(i - j);
            j = pf[j - 1];
        } else if (i < n && pat[j] != txt[i]) {
            if (j != 0) {
                j = pf[j - 1];
            } else {
                ++i;
            }
        }
    }
    return match;
}

std::vector<int> prefix_function(const std::string& s) {
    return prefix_function(std::vector<char>(s.begin(), s.end()));
}

std::vector<int> kmp(const std::string& txt, const std::string& pat,
                     const std::vector<int>& pf) {
    return kmp(std::vector<char>(txt.begin(), txt.end()),
               std::vector<char>(pat.begin(), pat.end()), pf);
}

template <int AlphabetSize, int Offset>
std::vector<std::vector<std::pair<int, bool>>> matching_automaton(
    const std::string& s) {
    const int n = s.size();
    auto lps = prefix_function(s);
    std::vector aut(n, std::vector<std::pair<int, bool>>(AlphabetSize));
    for (int i = 0; i < n; ++i) {
        for (int c = 0; c < AlphabetSize; ++c) {
            if (Offset + c == s[i]) {
                if (i == n - 1) {
                    aut[i][c] = {lps[i], true};
                } else {
                    aut[i][c] = {i + 1, false};
                }
            } else {
                aut[i][c] = {i > 0 ? aut[lps[i - 1]][c].first : 0, 0};
            }
        }
    }
    return aut;
}

#line 2 "string/kmp.hpp"
#include <string>
#include <vector>

template <typename T>
std::vector<int> prefix_function(const std::vector<T>& s) {
    const int n = s.size();
    std::vector<int> ret(n);
    for (int len = 0, i = 1; i < n; ++i) {
        if (s[i] == s[len]) {
            ++len;
            ret[i] = len;
        } else {
            if (len != 0) {
                len = ret[len - 1];
                --i;
            } else {
                ret[i] = 0;
            }
        }
    }
    return ret;
}

template <typename T>
std::vector<int> kmp(const std::vector<T>& txt, const std::vector<T>& pat,
                     const std::vector<int>& pf) {
    const int n = txt.size(), m = pat.size();
    std::vector<int> match;
    for (int i = 0, j = 0; i < n;) {
        if (pat[j] == txt[i]) {
            ++i;
            ++j;
        }
        if (j == m) {
            match.push_back(i - j);
            j = pf[j - 1];
        } else if (i < n && pat[j] != txt[i]) {
            if (j != 0) {
                j = pf[j - 1];
            } else {
                ++i;
            }
        }
    }
    return match;
}

std::vector<int> prefix_function(const std::string& s) {
    return prefix_function(std::vector<char>(s.begin(), s.end()));
}

std::vector<int> kmp(const std::string& txt, const std::string& pat,
                     const std::vector<int>& pf) {
    return kmp(std::vector<char>(txt.begin(), txt.end()),
               std::vector<char>(pat.begin(), pat.end()), pf);
}

template <int AlphabetSize, int Offset>
std::vector<std::vector<std::pair<int, bool>>> matching_automaton(
    const std::string& s) {
    const int n = s.size();
    auto lps = prefix_function(s);
    std::vector aut(n, std::vector<std::pair<int, bool>>(AlphabetSize));
    for (int i = 0; i < n; ++i) {
        for (int c = 0; c < AlphabetSize; ++c) {
            if (Offset + c == s[i]) {
                if (i == n - 1) {
                    aut[i][c] = {lps[i], true};
                } else {
                    aut[i][c] = {i + 1, false};
                }
            } else {
                aut[i][c] = {i > 0 ? aut[lps[i - 1]][c].first : 0, 0};
            }
        }
    }
    return aut;
}

Back to top page