题解 P3796 【【模板】AC自动机（加强版）】

Cekavis · 2017-06-15 22:33:16 · 题解

可能会是第一个题解...也只是来水一发

鉴于我水平太差,也没有完全理解这算法.甚至自己的程序(搬运了其他题)

各类资料应该也很多,丑陋的代码仅作为参考

#include<iostream>
#include<string.h> 
using namespace std;
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
const int MC=26;

struct T{//trie的一个结点吧..
  T *Pre[MC],*F;
  int Num;
  T(){memset(Pre,0,sizeof Pre),F=0,Num=0;}
}*R;

void I(char s[],int k){//插入一个模式串
  T *p=R;
  for(int i=0;s[i];i++){
    if(p->Pre[s[i]-'a']==0) p->Pre[s[i]-'a']=new T();
    p=p->Pre[s[i]-'a'];
  }
  p->Num=k;//仅仅记录该节点表示的模式串,如有重复模式串,应该会有问题
}

T *q[600005];

void Build(){//构造DFA
  int t=0;
  R->F=R;
  rep(j,0,MC-1) if(R->Pre[j]==0) R->Pre[j]=R;
    else{
      q[++t]=R->Pre[j];
      q[t]->F=R;
    }
  rep(cur,1,t){
    T *i=q[cur];
    rep(j,0,MC-1) if(i->Pre[j]!=0){
      T *k=i->F;
      while(k->Pre[j]==0) k=k->F;
      k=k->Pre[j];
      q[++t]=i->Pre[j];
      q[t]->F=k;
    }
  }
}

int n,ans,f[152];
char s[1000005],t[152][72];

int main(){
  cin>>n;
  while(n){
    R=new T();
    rep(i,1,n) scanf("%s",&t[i]),I(t[i],i);//插入模式串
    Build();
    scanf("%s",&s);
    T *cur=R;
    ans=0;
    for(int i=0;s[i];i++){
      int k=s[i]-'a';
      while(cur->Pre[k]==0) cur=cur->F;
      cur=cur->Pre[k];
      for(T *tmp=cur;1;tmp=tmp->F){
        ++f[tmp->Num];//            f[i]表示第i个模式串出现次数
        if(tmp==tmp->F) break;
      }
    }
    rep(i,1,n) ans=max(ans,f[i]);
    printf("%d\n",ans);
    rep(i,1,n) if(f[i]==ans) printf("%s\n",t[i]);
    cin>>n;
    memset(f,0,sizeof f);
  }
  return 0;
}