[Uva 1449][AC自動機] Dominating Patterns

原題連結
給出字串集合A和字串B，請找出A中出現在B最多次的字串，如果次數相同則按照出現順序輸出。

這是一個典型的多模板匹配問題，首先建構出A的AC自動機，拿B去匹配集合A裡的字串就相當於在AC自動機上轉移。
剩下的只要按照AC自動機的定義去做就可以了。
不過code並沒有採用最簡單的方法，也就是每找到一個單字節點就往回更新（當然這樣做對於本題來說複雜度也是好的)，而是讓所有B走訪到的節點cnt++，最後再進行一次dp，這樣會有更好的複雜度上界，實際表現也快了約1.5倍左右。

#include<bits/stdc++.h>
using namespace std;
const int maxnode=100000+5;
const int maxlen=1000000+5;
const int maxn=150+5;
const int INF=(1<<30);
const int SIGMA_SIZE=26;
struct Node
{
    Node *ch[SIGMA_SIZE],*fail,*last;
    int cnt,ed;
    void init() {memset(ch,0,sizeof ch);cnt=ed=0;fail=last=NULL;}
} mem[maxnode],*root;
struct AhoCorasick
{
    Node* ednode[maxn];
    int size;
    inline void init() {root=&mem[0];mem[0].init();size=0;}
    inline int idx(char c){return c-'a';}
    void insert(char* s,int v)
    {
        Node* now=root;
        for(int i=0;s[i];i++)
        {
            int c=idx(s[i]);
            if(!now->ch[c]) {now->ch[c]=&mem[++size];mem[size].init();}
            now=now->ch[c];
        }
        now->ed=1;
        ednode[v]=now;
    }
    void getfail()
    {
        queue<Node*> Q;
        Q.push(root);
        while(!Q.empty())
        {
            Node* now=Q.front();Q.pop();
            for(int i=0;i<SIGMA_SIZE;i++)
            {
                if(!now->ch[i]) continue;
                Node* nx=now->ch[i],*j=now->fail;
                while(j && !j->ch[i]) j=j->fail;
                nx->fail=j?j->ch[i]:root;
                nx->last=nx->fail->ed?nx->fail:nx->fail->last;
                Q.push(nx);
            }
        }
    }
    void find(char *T)
    {
        Node* now=root;
        for(int i=0;T[i];i++)
        {
            int c=idx(T[i]);
            while(now && !now->ch[c]) now=now->fail;
            if(!now) now=root;
            else now=now->ch[c];
            now->cnt++;
        }
    }
    void print(int n,char A[][75])
    {
        for(int i=size;i>=0;i--) if(mem[i].fail) mem[i].fail->cnt+=mem[i].cnt;
        int ans=-INF;
        for(int i=0;i<=size;i++) if(mem[i].ed) ans=max(ans,mem[i].cnt);
        printf("%d\n",ans);
        for(int i=0;i<n;i++) if(ednode[i]->cnt==ans) printf("%s\n",A[i]);
    }
}AC;
char s[maxlen],A[maxn][75];
int main()
{
    int N;
    while(scanf("%d",&N)==1 && N)
    {
        AC.init();
        for(int i=0;i<N;i++)
        {
            scanf("%s",A[i]);
            AC.insert(A[i],i);
        }
        AC.getfail();
        scanf("%s",s);
        AC.find(s);
        AC.print(N,A);
    }
}