分析

非常好的一道题，用到的 也是在 中非常有意思的，考察了多方面的知识。我把考察的知识写在了下面。

• 一个串出现的次数等同于 。就是在 指针构成的反树链上的权值。

• 基本的差分和数据结构。

• 由于我们有了性质一，那么我们对于一个串的插入其实就是子树 ，删除反之。而对于子树操作可以用树链剖分也可以用树状数组维护差分维护一下 区间。那么总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
bool vis[N];
int pos[N];
struct BitTree {
    int t[N],limit;
    void add(int x,int k) {for(int i = x;i <= limit;i += i & -i) t[i] += k;}
    int ask(int x) {int tot = 0;for(int i = x;i;i -= i & -i) tot += t[i];return tot;}
    void plus(int l,int r,int k) {add(l,k);add(r + 1,-k);}
    void del(int l,int r,int k) {plus(l,r,-k);} 
}T;
struct Tree {
    vector<int> G[N];
    int L[N],R[N],Id;
    void addedge(int x,int y) {G[x].push_back(y);}
    void dfs(int x) {L[x] = ++Id;for(auto y:G[x]) dfs(y);R[x] = Id;}
}t;
struct ACAM {
    int size,ch[N][26],fail[N];
    void insert(char *s,int id) {
        int u = 0,len = strlen(s + 1);
        for(int i = 1;i <= len;i++) {
            int c = s[i] - 'a';
            if(!ch[u][c]) ch[u][c] = ++size;
            u = ch[u][c];
        }
        pos[id] = u;
    }
    void build() {
        queue<int> q;for(int i = 0;i < 26;i++) if(ch[0][i]) q.push(ch[0][i]);
        while(!q.empty()) {
            int x = q.front();q.pop();for(int i = 0;i < 26;i++) {
                int &y = ch[x][i];if(y) {fail[y] = ch[fail[x]][i];q.push(y);}
                else y = ch[fail[x]][i];
            }
        }
        for(int i = 1;i <= size;i++) t.addedge(fail[i],i);
    }
}ac;
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++) {
        static char S[N];scanf("%s",S + 1);
        ac.insert(S,i);    
    }
    ac.build();t.dfs(0);T.limit = ac.size + 1;
    for(int i = 1;i <= m;i++) T.plus(t.L[pos[i]],t.R[pos[i]],1),vis[i] = 1;
    while(n--) {
        static char S[N];scanf("%s",S + 1);
        if(S[1] == '?') {
            int len = strlen(S + 1),ans = 0,u = 0;
            for(int i = 2;i <= len;i++) {
                int c = S[i] - 'a';u = ac.ch[u][c];ans += T.ask(t.L[u]);
            }
            printf("%d\n",ans);
        }
        if(S[1] == '-') {
            int len = strlen(S + 1),u = 0;
            for(int i = 2;i <= len;i++) u = u * 10 + S[i] - '0';
            if(vis[u] == 0) continue;vis[u] = 0;
            T.del(t.L[pos[u]],t.R[pos[u]],1);
        }
        if(S[1] == '+') {
            int len = strlen(S + 1),u = 0;
            for(int i = 2;i <= len;i++) u = u * 10 + S[i] - '0';
            if(vis[u] == 1) continue;vis[u] = 1;
            T.plus(t.L[pos[u]],t.R[pos[u]],1);
        }
    }
    return 0;
}