Preffix Function

vector<int> preffix_function(string &s) {
  int N = s.length();
  vector<int> pi(N + 1);
  s = '#' + s;
  for (int i = 2, q = 0; i <= N; ++i) {
    while (q && s[q + 1] != s[i])
      q = pi[q];
    if (s[q + 1] == s[i])
      ++q;
    pi[i] = q;
  }
  return pi;
}