题解 P5357 【【模板】AC自动机（二次加强版）】
前言
此处仅讲AC自动机的优化,刚开始学的请右转:
AC自动机【简单版】
AC自动机【加强版】
顺带宣传下yyb巨佬的博客(相当透彻)
首先,既然是输出每个串(还有重复),那么只需一个vector[]存就好了
但既然是二次加强版,那肯定会有TLE
于是匹配方面马上就能看到可以优化的地方
原匹配
unsigned int p=0;
register char c=getchar();
while('a'>c||c>'z') c=getchar();
for(;'a'<=c&&c<='z';c=getchar()){
c-='a';
p=all[p].next[c];
for(register int id=p;id!=0;id=all[id].nxt)
all[id].count++;//此处我们用一个循环来记录
}很明显,此处用循环效率明显太低了!
如果模式串为rrrrrrr...(长度为n),将会循环n次
时间复杂度将退化为单个KMP的 O(n*m)
于是就能想到只记录AC自动机扫描到的位置,之后统一递归处理
unsigned int p=0;
register char c=getchar();
while('a'>c||c>'z') c=getchar();
for(;'a'<=c&&c<='z';c=getchar()){
c-='a';
p=all[p].next[c];
all[p].count++;
}
for(register int i=size;i>0;i--) //统一处理
all[all[i].nxt].count+=all[i].count;优化的差不多了,时间复杂度达到了稳定的 O(n+m)
从后往前递归，fail数应该符合这一规律
交吧! WA?!
时间复杂度是够了,但为甚么答案错了?
如果是普通KMP,nxt只会指向模式串本身的前缀
但AC自动机由于是字典树,指向的不一定是前缀
因此存储整个fail指针树,依序dfs就真的必要了
(原以为可以多省点空间的qwq)
求nxt的时候,存儿子首选邻接表
if(head[nextnxt]==0)
head[nextnxt]=all[id].next[i];
else next[tail[nextnxt]]=all[id].next[i];
tail[nextnxt]=all[id].next[i];
next[all[id].next[i]]=0;然后统计便这样写
inline void dfs_count(int id){
for(register int i=head[id];i!=0;i=next[i]){
dfs_count(i);
all[id].count+=all[i].count;
}
}于是这道题差不多就完成了~
AC完整代码(不开O2,1.40s,35.76MB)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
inline int read(){
register char c=getchar(),w=1;
while('0'>c||c>'9'){
if(c=='-') w=-1;
c=getchar();
}
register int a=0;
while('0'<=c&&c<='9'){
a=a*10+c-'0';
c=getchar();
}
return a*w;
}//快读(尽管基本没用)
template<unsigned int size>
class QUEUE{//求nxt的队列
private:
unsigned int list[size+1];
unsigned int head,tail;
public:
QUEUE(){
head=tail=0;
}
inline void push(unsigned int in){
list[tail]=in;
if(tail==size) tail=0;
else tail++;
}
inline void pop(){
if(head==size) head=0;
else head++;
}
inline unsigned int top(){return list[head];}
inline bool empty(){return head==tail;}
};
QUEUE<200000>q;
template<unsigned int length,unsigned int S_SIZE>
class Trie{
private:
struct point{
unsigned int next[26],nxt;
unsigned int count,floor,ans;
}all[length+1];
unsigned int size,s_size;
unsigned int vector[S_SIZE+1],head[length+1],tail[length+1],next[length+1];
public:
Trie(){//字典树初始化
s_size=size=0;
}
inline void read(){//读入
unsigned int p=0;
register char c=getchar();
while('a'>c||c>'z') c=getchar();
for(;'a'<=c&&c<='z';c=getchar()){
c-='a';
if(all[p].next[c]==0){
size++;
all[p].next[c]=size;
all[size].floor=all[p].floor+1;
}
p=all[p].next[c];
}
s_size++;//更新向量
vector[s_size]=p;
}
inline void getnxt(){//求nxt(或fail指针)
for(register int i=0;i<26;i++){
if(all[0].next[i]!=0){
all[all[0].next[i]].nxt=0;
if(head[0]==0) head[0]=all[0].next[i];
else next[tail[0]]=all[0].next[i];
tail[0]=all[0].next[i];
next[all[0].next[i]]=0;
//邻接表存nxt树儿子
q.push(all[0].next[i]);
}
}
for(register int id;!q.empty();){
id=q.top();q.pop();
for(register int i=0,nextnxt;i<26;i++){
nextnxt=all[all[id].nxt].next[i];
if(all[id].next[i]==0){
all[id].next[i]=nextnxt;
continue;
}
all[all[id].next[i]].nxt=nextnxt;
if(head[nextnxt]==0)
head[nextnxt]=all[id].next[i];
else next[tail[nextnxt]]=all[id].next[i];
tail[nextnxt]=all[id].next[i];
next[all[id].next[i]]=0;
//同上
q.push(all[id].next[i]);
}
}
}
inline void dfs_count(int id){
for(register int i=head[id];i!=0;i=next[i]){
dfs_count(i);
all[id].count+=all[i].count;
}
}//依序统计
inline void AC_auto(){
unsigned int p=0;
register char c=getchar();
while('a'>c||c>'z') c=getchar();
for(;'a'<=c&&c<='z';c=getchar()){
c-='a';
p=all[p].next[c];
all[p].count++;
}//匹配
dfs_count(0);
for(register unsigned int i=1;i<=s_size;i++){
printf("%d\n",all[vector[i]].count);
}//输出
}
};
Trie<200010,200010> tree;
int main(){
const int n=read();
for(register int i=0;i<n;i++) tree.read();
tree.getnxt();
tree.AC_auto();
return 0;
}