1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

vi pre(string s) {
    int n = s.size();
    vi nxt(n);
    for (int i = 1; i < n; i++) {
        int j = nxt[i - 1];
        while (j > 0 && s[j] != s[i]) j = nxt[j - 1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}