Gym 101741 K（AC自动机）

传送门

题意：

给你一个长度为nnn的模式串以及mmm个总长度长度不超过10510^5105的匹配串。问这mmm个匹配串分别在模式串中出现了多少次，要求每一次出现位置不能够相交。

题目分析：

首先，我们要知道，虽然匹配串的总长度为10510^5105，但是因为KMP的时间复杂度为O(n+m)\mathcal{O}(n+m)O(n+m)，这就使得整体复杂度总会变成O(n2)\mathcal{O}{(n^2)}O(n2)，因此KMP显然是会超时的。

因为涉及多串匹配的问题，因此我们可以往AC自动机方向去考虑。我们首先离线将询问的所有字符串建立出AC自动机，之后我们只需要用模式串在AC自动机上去匹配即可。

但是该问题的特殊点在于：两个能够在模式串中匹配的串不能够有相交部分。对于这一点，我们只需要在普通的查询中进行修改；我们需要记录一下在AC自动机匹配到字符串strstrstr（我们设该状态在自动机上的ididid为iii）的位置pos(i)pos(i)pos(i)，以及strstrstr前一个被匹配了的位置lastpos(i)lastpos(i)lastpos(i)。我们可以发现，如果当前匹配的位置与之前匹配之差小于当前字符串的长度∣str∣|str|∣str∣，即pos(i)−lastpos(i)>=∣str∣pos(i)-lastpos(i)>=|str|pos(i)−lastpos(i)>=∣str∣则说明在当前位置pos(i)pos(i)pos(i)下，能够对答案有贡献，我们使该匹配串的答案加111即可。

最后我们只需要维护一下匹配串的终点位置，最后输出答案即可。

代码：

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
char st[maxn],st1[maxn];
struct Trie{
    int next[maxn<<2][26],End[maxn<<2],root,fail[maxn<<2],id;
    int cnt[maxn<<2],last[maxn<<2],Len[maxn<<2];
    int newnode(){
        for(int i=0;i<26;i++){
            next[id][i]=-1;
        }
        Len[id]=0;
        return id++;
    }
    void init(){
        id=0;
        root=newnode();
    }
    void Insert(char *str,int id){
        int len=strlen(str);
        int now=root;
        for(int i=0;i<len;i++){
            if(next[now][str[i]-'a']==-1)
                next[now][str[i]-'a']=newnode();
            Len[next[now][str[i]-'a']]=Len[now]+1;
            now=next[now][str[i]-'a'];
        }
        End[id]=now;
        Len[now]=len;
    }
    void build(){
        queue<int>que;
        int now=root;
        fail[root]=root;
        for(int i=0;i<26;i++){
            if(next[root][i]==-1){
                next[root][i]=root;
            }
            else{
                fail[next[root][i]]=root;
                que.push(next[root][i]);
            }
        }
        while(!que.empty()){
            now=que.front();
            que.pop();
            for(int i=0;i<26;i++){
                if(next[now][i]==-1)
                    next[now][i]=next[fail[now]][i];
                else{
                    fail[next[now][i]]=next[fail[now]][i];
                    que.push(next[now][i]);
                }
            }
        }
    }
    void query(char *str){
        int len=strlen(str);
        for(int i=0;i<id;i++) cnt[i]=0,last[i]=-1;
        int now=root;
        for(int i=0;i<len;i++){
            now=next[now][str[i]-'a'];
            int tmp=now;
            while(tmp!=root){
                if(i-last[tmp]>=Len[tmp]){
                    cnt[tmp]++;
                    last[tmp]=i;
                }
                tmp=fail[tmp];
            }
        }
    }
}ac;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    ac.init();
    scanf("%s",st);
    for(int i=1;i<=m;i++){
        scanf("%s",st1);
        ac.Insert(st1,i);
    }
    ac.build();
    ac.query(st);
    for(int i=1;i<=m;i++){
        printf("%d\n",ac.cnt[ac.End[i]]);
    }
    return 0;
}
           

转载于:https://www.cnblogs.com/Chen-Jr/p/11007160.html