LUOGU3976 AC自动机

作者: 苏子旃 | 来源:发表于2019-02-16 15:09 被阅读0次

LUOGU3976 AC自动机
AC自动机专题整理
自动AC机？不，是AC自动机
【AC自动机】AC自动机可以帮你自动AC吗
AC自动机-去除敏感字符
lucene中文分词
字符串算法小结
AC 自动机
回文树（附模板题URAL-1960）
AC自动机_模板

LUOGU3808
LUOGU3976
Description
有 $N$ 个由小写字母组成的模式串以及一个文本串 $T$ 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 $T$ 中出现的次数最多。
Input Format
输入含多组数据。
每组数据的第一行为一个正整数 $N$ ，表示共有 $N$ 个模式串， $1 \leq N \leq 150$ 。
接下去 $N$ 行，每行一个长度小于等于 $70$ 的模式串。下一行是一个长度小于等于 $10^6$ 的文本串 $T$ 。
输入结束标志为 $N=0$ 。

Output Format
对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

Sample Input

2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0

Sample Output

4
aba
2
alpha
haha

Constraints
见题面。

CCYOS
这是一道AC自动机的板子题。

AC自动机 可以理解为在Trie图上的KMP算法。

这是一棵trie树
对于正常的遍历，每次在这棵树上搜索的时候会因为回溯而浪费大量时间。因此我们考虑对它进行优化，直接建立“树边”：搜索时，在当前节点的儿子中下一个字符失配时，能够快速地跳转到下一个可以匹配下一个字符的节点，也就是当前可匹配的最长后缀。
设当前节点为 $i$ ，则当前节点的“树边”指向 $nxt[i]$ 。
建立nxt数组
举一个更详细的例子：详细的例子
对文本串 ader 进行匹配时，发现在匹配至8号节点时失配，于是直接跳转到10号节点继续进行匹配。
如何建立nxt数组 - get_nxt
根节点的后继是0，根节点的直接下属结点的后继也是0。（重新开始匹配）
余下的结点的后继：设到节点 $x$ 上的边的字符为 $k$ ，父亲结点为 $f$ ，则 $nxt[x] = ch[nxt[f]][k]$ 。

code

inline void get_nxt(){
  int now = 0;
  queue<int> q;while(q.size())q.pop();
  for(int i = 0;i < 26;++i)if(ch[0][i])q.push(ch[0][i]);
  while(q.size()){
    now = q.front();q.pop();
    for(int i = 0;i < 26;++i){
      if(ch[now][i])q.push(ch[now][i]),nxt[ch[now][i]] = ch[nxt[now]][i];
      else ch[now][i] = ch[nxt[now]][i];
    }
  }
}

trie树的建立
先沿着树搜索，在空点处加点，标记最后一个字符声明这是一个字符串的结尾。记树的节点数为 $cnt$ 。

code

int cnt;
inline void build(char* s){
  int now = 0,len = strlen(s);
  for(int i = 0;i < len;++i){
    int c = s[i] - 'a';
    if(!ch[now][c])ch[now][c] = ++cnt;
    now = ch[now][c];
  }
  ed[now] = 1;
}

trie树的搜索
计数式：沿着树搜索，向下一层，搜索后继结点计数。
bool式：勇就完事了。

code

//计数式
inline void ask(char* s){
  int now = 0,len = strlen(s);
  for(int i = 0;i < len;++i){
    now = ch[now][s[i] - 'a'];
    for(int t = now;t;t = nxt[t])ans[ed[t]]++;
  }
}
//bool式
inline bool ask(char* s){
  int len = strlen(s),now = 0;
  now = ch[now][s[i] - 'a'];
  if(end[now])return 1;
  }
  return 0;
}

多组数据一定要清空全部数组。
code

#include<bits/stdc++.h>
using namespace std;

int N,tot;
int ch[1000005][30],nxt[1000005],endd[1000005],cnt[155];
struct str{
    char a[75];
}inn[155];
char in[1000005];
struct Ans{
    int num,id;
}ans[155];
inline bool cmp(Ans a,Ans b){
    if(a.num == b.num)return a.id < b.id;
    return a.num > b.num;
}

inline void build(char* s,int id){
    int len = strlen(s);int now = 0;
    for(int i = 0;i < len;++i){
        int c = s[i] - 'a';
        if(!ch[now][c])ch[now][c] = ++tot;
        now = ch[now][c];
    }
    endd[now] = id;
}

inline void get_nxt(){
    queue<int> q;while(q.size())q.pop();
    for(int i = 0;i < 26;++i)if(ch[0][i])q.push(ch[0][i]);
    int now = 0;
    while(q.size()){
        now = q.front();q.pop();
        for(int i = 0;i < 26;++i){
            if(!ch[now][i])ch[now][i] = ch[nxt[now]][i];
            else nxt[ch[now][i]] = ch[nxt[now]][i],q.push(ch[now][i]);
        }
    }
}

inline void ask(char* s){
    int len = strlen(s),now = 0;
    for(int i = 0;i < len;++i){
        int c = s[i] - 'a';
        now = ch[now][c];
        for(int t = now;t;t = nxt[t])++ans[endd[t]].num;
    }
    sort(ans + 1,ans + 155,cmp);
    int num = ans[1].num;
    printf("%d\n",num);
    for(int i = 1;i <= 150&&ans[i].num == num;++i)printf("%s\n",inn[ans[i].id].a);
}

int main(){
    freopen("3796-1.in","r",stdin);
    scanf("%d",&N);
    while(N){
        tot = 0;
        for(int i = 1;i <= N;++i){
            scanf("%s",inn[i].a);
            ans[i].id = i,ans[i].num = 0;
            build(inn[i].a,i);
        }
        get_nxt();
    //  cout<<"                                             over"<<endl;
        scanf("%s",in);
        ask(in);
        memset(ch,0,sizeof ch);
        memset(nxt,0,sizeof nxt);
        memset(endd,0,sizeof endd);
        scanf("%d",&N);
    }
    return 0;
}