P5357

发表于 更新于 分类于
【模板】AC 自动机（二次加强版）

【模板】AC 自动机（二次加强版）

论为何 lrj 的书上的 AC 自动机是假的。。。

暴力跳 $nxt$ 来计数实际上复杂度是假的。。。

因为我们完全有线性方法解决。。。

重温了一遍 AC 自动机。

给一下原来的 博客地址。

这里这个模板的数据比较大，而且有重复的模式串，所以需要稍微修改一下程序。

首先，我们要动态分配模式串内存，用个指针加上内存池即可。

然后就是处理重复的模式串，保证每个模式串的出现次数是 1，并且重复的模式串我们尝试让它们指向同一个标号来去重和输出答案。

好像没了。

不知道怎么卡常，不开 O2 的话其实有一个点过不掉。。。

真相察觉了，这个题数据比较水，像我这种暴力跳 $nxt$ 的只要常数不太离谱仍然可以水过。

正确做法是记录节点匹配次数之后最后再在自动机上 DP 求出每个节点的答案。

代码咕了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll N=7e6;

ll n,tot;
ll id[N+5],ans[N+5],cnt[N+5],trie[N+5][26],nxts[N+5],lst[N+5],vt[N+5];
bool vis[N+5];
char buft[N+5];
char tmp[N+5],s[N+5],*t[N+5];
char *nowt=buft;

inline ll ins(char *str) {
  ll len=strlen(str),p=0;
  for(ll k=0;k<len;k++) {
    ll ch=str[k]-'a';if(!trie[p][ch]) trie[p][ch]=++tot;p=trie[p][ch];
  }
  cnt[p]=1;return p;
}

inline void count(ll j) {
  if(j) {ans[id[j]]+=cnt[j];count(lst[j]);}
}

inline void AC_Pre() {
  queue<ll> q;nxts[0]=0;
  for(ll c=0;c<26;c++) {
    ll u=trie[0][c];
    if(u) {nxts[u]=0;q.push(u);lst[u]=0;}
  }
  while(!q.empty()) {
    ll h=q.front();q.pop();
    for(ll c=0;c<26;c++) {
      ll u=trie[h][c];
      if(!u) {trie[h][c]=trie[nxts[h]][c];continue;}
      q.push(u);ll v=nxts[h];
      while(v&&!trie[v][c]) v=nxts[v];
      nxts[u]=trie[v][c];lst[u]=cnt[nxts[u]]?nxts[u]:lst[nxts[u]];
    }
  }
}

inline void AC(char *str) {
  ll len=strlen(str),j=0;
  for(ll i=0;i<len;i++) {
    ll c=str[i]-'a';j=trie[j][c];
    if(cnt[j]) count(j);
    else {if(lst[j]) count(lst[j]);}
  }
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {
  
  n=read();
  
  for(ll i=1;i<=n;i++) {
    t[i]=nowt;
    scanf("%s",t[i]);nowt+=strlen(t[i])+2;
    ll tmp=ins(t[i]);
    if(!id[tmp]) id[tmp]=i;vt[i]=id[tmp];
  }
  
  AC_Pre();scanf("%s",s);AC(s);
  
  for(ll i=1;i<=n;i++) {if(vt[i]) writeln(ans[vt[i]]);}
  
  return 0;
}