strings/KMP.h

• View this file on GitHub
• Last update: 2025-11-14 00:13:37+07:00

Code

vi pi(const string& s) {
  vi p(sz(s));
  for (int i = 1; i < sz(s); ++i) {
    int 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 "strings/KMP.h"
vi pi(const string& s) {
  vi p(sz(s));
  for (int i = 1; i < sz(s); ++i) {
    int 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