Castle

KMP
如果集合中有一个字符串 Si长度为i，而且为当前 S 的后缀，那么所有比 i 长度小的都会是 S 的后缀（如果存在于集合），所以求出每个当前 S 的后缀最长匹配前面的长度为多少，再用树状数组或前缀和统计在这长度以内加入了集合的有多少个就行了。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1300000;
int sum[maxn], f[maxn], n, m, op, t;
char s[maxn], c;
bool p[maxn] = {0};

char get_char() {
    char o = ' ';
    while (!(o >= 'a' && o <= 'z')) o = getchar();
    return o;
}

int get_int() {
    char o = ' ';
    while (!(o >= '0' && o <= '9')) o = getchar();
    return o-'0';
}

int main() {
    scanf("%d %d", &n, &m);
    scanf("%s", s+1);
    memset(f, 0, sizeof(f));
    for (int i = 2; i <= n; i++) {
        t = f[i-1];
        while (t && s[i] != s[t+1]) t = f[t];
        if (s[i] == s[t+1]) f[i] = t+1;
        else f[i] = 0;
    }
    while (m--) {
        op = get_int();
        if (op == 1) {
            c = get_char();
            s[++n] = c;
            t = f[n-1];
            while (t && s[n] != s[t+1]) t = f[t];
            if (s[n] == s[t+1]) {
                sum[n] = sum[t+1];
                f[n] = t+1;
            } else f[n] = 0;
        } else if (op == 2) {
            if (!p[n]) {
                p[n] = true;
                sum[n]++;
            }
        } else {
            printf("%d\n", sum[n]);
        }
    }
}