string/kmp.hpp

• View this file on GitHub
• Last update: 2026-04-05 00:48:27+09:00
• Include: #include "string/kmp.hpp"
• Link: https://codeforces.com/contest/2209/problem/E

Code

// KMP[n]: longest border length of S[0,n) or 0.
// https://codeforces.com/contest/2209/problem/E
template <typename STRING>
vector<int> kmp(const STRING& S) {
  int N = len(S);
  vc<int> ANS(N + 1);
  FOR(n, 2, N + 1) {
    int k = ANS[n - 1];
    while (k > 0 && S[k] != S[n - 1]) k = ANS[k];
    ANS[n] = k + (S[k] == S[n - 1]);
  }
  return ANS;
}

#line 1 "string/kmp.hpp"

// KMP[n]: longest border length of S[0,n) or 0.
// https://codeforces.com/contest/2209/problem/E
template <typename STRING>
vector<int> kmp(const STRING& S) {
  int N = len(S);
  vc<int> ANS(N + 1);
  FOR(n, 2, N + 1) {
    int k = ANS[n - 1];
    while (k > 0 && S[k] != S[n - 1]) k = ANS[k];
    ANS[n] = k + (S[k] == S[n - 1]);
  }
  return ANS;
}

Back to top page