KMP 法 (Knuth–Morris–Pratt algorithm)
(src/string/KMP.hpp)

• View this file on GitHub
• Last update: 2024-05-31 19:00:40+09:00
• Include: #include "src/string/KMP.hpp"

• 参考実装：KACTL

使い方

• vector<ll> KMP(string s)：$\text{kmp}[i] := \max\{ l ≤ i \mid s[:l] = s[(i+1)-l:i+1] \}$ で定義される配列 $\text{kmp}$ を求める

$O(n)$ 時間

Verified with

• test/string/KMP.test.cpp

Code

// kmp[i] := max{ l ≤ i | s[:l] == s[(i+1)-l:i+1] }
// abacaba -> 0010123
auto KMP(string s) {
   vector<ll> p(sz(s));
   rep(i, 1, sz(s)) {
      ll g = p[i - 1];
      while(g && s[i] != s[g]) g = p[g - 1];
      p[i] = g + (s[i] == s[g]);
   }
   return p;
}

#line 1 "src/string/KMP.hpp"
// kmp[i] := max{ l ≤ i | s[:l] == s[(i+1)-l:i+1] }
// abacaba -> 0010123
auto KMP(string s) {
   vector<ll> p(sz(s));
   rep(i, 1, sz(s)) {
      ll g = p[i - 1];
      while(g && s[i] != s[g]) g = p[g - 1];
      p[i] = g + (s[i] == s[g]);
   }
   return p;
}

Back to top page