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