[NOI(P?)2017模拟]字符串

2017.10.16 T3 1985

样例数据
输入

3 5
ab
bc
abc
acbcb
2 b
3 c
4 a
1 b
3 a

输出

1
2
3
4
2
1

分析：很久没碰NOI内容，完全没想到这道题是AC自动机（考试时完全忘了老师说过T3会加入NOI内容orz），由于T2调了半天，只能花20分钟KMP暴力，刷了20分。
当然，光用AC自动机是肯定AC不了的（理解成用来AC的自动机AC不了23333），还要有一个结论：修改的当前点只会导致起始和终点在[pos-|T|，pos+|T|]这个范围内的匹配改变。
所以，只需要把s的这个子串[pos-|T|，pos+|T|]放入AC自动机中求匹配数，调整答案即可。
复杂度O( |T|Q )。

代码

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

int getint()
{
    int sum=0,f=1;
    char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }
    for(;isdigit(ch);ch=getchar())
        sum=(sum<<3)+(sum<<1)+ch-48;
    return sum*f;
}

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

void buildtree()
{
    int len=strlen(s+1);
    if(len>maxl) maxl=len;
    int u=1;
    for(int i=1;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 addfail()
{
    que.push(1);
    while(!que.empty())
    {
        int u=que.front(),w;
        que.pop();
        for(int i=0;i<26;i++)
        {
            int 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.push(w);
                trie[w].cnt+=trie[v].cnt;
            }
            else 
                trie[u].son[i]=v;
        }
    }
}

int  find()
{
    int now=1;
    int tmp;
    int ans=0;
    for(int i=start;i<=end;i++)
    {
        now=trie[now].son[s[i]-'a'];
        ans+=trie[now].cnt;
    }
    return ans;
}

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

    for(int i=0;i<26;i++)
        trie[0].son[i]=1;
    n=getint();m=getint();
    tot=1;
    for(int i=1;i<=n;i++)//把所有的t丢到trie树中
    {
        scanf("%s",s+1);
        buildtree();
    }

    addfail();//建fail指针
    scanf("%s",s+1);
    len=strlen(s+1);
    start=1;end=len;
    ans=find();//用s去匹配，求出原始答案
    printf("%d\n",ans);
    for(int i=1;i<=m;i++)//修改操作
    {
        pos=getint();scanf("%c",&c);
        start=max(pos-maxl,1);
        end=min(pos+maxl,len);
        ans-=find();//将原来串中能匹配的减去
        s[pos]=c;
        ans+=find();//加上修改后能匹配的（如果以前就能匹配的没有被修改影响，那么在加的时候也能匹配并加回去，所以不存在把本来能匹配的被错减的情况）
        cout<<ans<<'\n';
    }

    return 0;
}

本题结。