[NOIP模拟][AC自动机]字符串

样例输入：

3 5

ab

bc

abc

acbcb

2 b

3 c

4 a

1 b

3 a

样例输出：

1

2

3

4

2

1

题目分析：

如果没有修改操作就是AC自动机模板题。记录n个字符串T中最长的长度为maxt，每次修改位置pos上的字符，其实它只会影响区间[pos-maxt,pos+maxt]，所以先将原ans减去这段区间的贡献，再加上替换字符后这段区间的贡献。

附代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cmath>
#include<cstring>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std;

struct node{
    int cnt;
    int fail;
    int son[];
}trie[];
int t,tot,n,vst[],ans,m,pos,maxl,len,maxlen,start,end;
char s[],c;

int readint()
{
    char ch;int i=,f=;
    for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-') {ch=getchar();f=-;}
    for(;ch>='0'&&ch<='9';ch=getchar()) i=(i<<)+(i<<)+ch-'0';
    return i*f;
}

void create()//建trie树
{
    int len=strlen(s+);
    if(len>maxl) maxl=len;
    int u=;
    for(int i=;i<=len;i++)
    {
        if(!trie[u].son[s[i]-'a'])
            trie[u].son[s[i]-'a']=++tot;
        u=trie[u].son[s[i]-'a'];
    }
    trie[u].cnt++;
}

void createfail()//建fail指针
{
    static int qn,que[];
    que[qn=]=;
    for(int ql=;ql<=qn;ql++)
    {
        int u=que[ql],v,w;
        for(int i=;i<;i++)
        {
            v=trie[u].fail;
            while(!trie[v].son[i])
                v=trie[v].fail;
            v=trie[v].son[i];w=trie[u].son[i];
            if(w)
                {
                    trie[w].fail=v;
                    que[++qn]=w;
                    trie[w].cnt+=trie[v].cnt;//这里加上其fail指针指向的位置的个数，在询问时就不用跳fail指针了，更节约时间
                }
            else 
                trie[u].son[i]=v;
        }
    }
}

int  find()
{
    int now=;
    int tmp;
    int ans=;
    for(int i=start;i<=end;i++)
    {
        now=trie[now].son[s[i]-'a'];
        ans+=trie[now].cnt;//因为上面的操作就不用跳fail指针，直接加就行
    }
    return ans;
}

int main()
{
    //freopen("string.in","r",stdin);
    //freopen("string.out","w",stdout);

    for(int i=;i<;i++)
        trie[].son[i]=;
    n=readint();m=readint();
    tot=;
    for(int i=;i<=n;i++)
    {
        scanf("%s",s+);
        create();
    }
    createfail();
    scanf("%s",s+);
    len=strlen(s+);
    start=;end=len;
    ans=find();
    printf("%d\n",ans);
    for(int i=;i<=m;i++)
    {
        pos=readint();scanf("%c",&c);
        start=max(pos-maxl,);end=min(pos+maxl,len);
        ans-=find();
        s[pos]=c;
        ans+=find();
        cout<<ans<<endl;//printf("%d\n",ans);
    }

    return ;
}