string s;
int pref[SZ];

void build_pref() {
    pref[0] = 0;
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && s[pref[j - 1]] != s[i])
            j = pref[j - 1];
        if (j == 0)
            pref[i] = 0;
        else
            pref[i] = pref[j - 1] + 1;
    }
}