KMP

const int N = 1e6+7;
string s;
int kmp[N];

void buildKMP() {
    kmp[0] = 0;
    for (int i = 1; i < s.size(); ++i) {
        int k = kmp[i-1];
        while (k > 0 && s[k] != s[i]) {
            k = kmp[k-1];
        }
        kmp[i] = k + (s[k]==s[i]);
    }
}

int aut[N][26];

void buildAutomaton() {
    s += '#';
    for (int i = 0; i < s.size(); ++i)
    for (int c = 0; c < 26; ++c) { // 'a' -> 'z'
        if (i > 0 && c+'a' != s[i]) {
            aut[i][c] = aut[kmp[i-1]][c];
        }
        else {
            aut[i][c] = i + (c+'a' == s[i]);
        }
    }
}