题意
某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。
给出一个由若干单词组成的单词表,问每个单词在这个表中出现了几次.
分析
参照jklover的题解。
很像一个 kmp 或是 AC 自动机裸题,然而并没有那么简单.用自动机做 n 次匹配,可能会被卡掉.如果一直跳 fail 指针,就可以构造一组数据让你一直跳.
正确的做法是使用 fail 树,连出这样所有的有向边 fail[x]−>x .自动机上,每个节点都代表了一个前缀,连出边后,可以发现父亲节点是儿子节点的后缀.
而一个字符串被匹配的次数恰好等于以它为后缀的前缀数目,即 fail 树中子树的大小.
插入字符串的时候将经过的每个节点的权值 +1 ,最后 dfs 统计即可.
时间复杂度:线性。
代码
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
rg T data=0;
rg int w=1;
rg char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
{
data=data*10+ch-'0';
ch=getchar();
}
return data*w;
}
template<class T>il T read(rg T&x)
{
return x=read<T>();
}
typedef long long ll;
co int N=1e6+1,S=26;
int n;
namespace AC
{
int idx;
int ch[N][S],fail[N],val[N];
int nx[N],to[N],siz[N];
int pos[N];
void ins(char*s,int len,int v)
{
int u=0;
for(int i=0;i<len;++i)
{
int k=s[i]-'a';
if(!ch[u][k])
ch[u][k]=++idx;
u=ch[u][k];
++val[u];
}
pos[v]=u;
}
void getfail()
{
std::queue<int>Q;
for(int i=0;i<S;++i)
if(ch[0][i])
Q.push(ch[0][i]);
while(Q.size())
{
int u=Q.front();Q.pop();
nx[u]=to[fail[u]],to[fail[u]]=u;
for(int i=0;i<S;++i)
{
if(ch[u][i])
{
fail[ch[u][i]]=ch[fail[u]][i];
Q.push(ch[u][i]);
}
else
ch[u][i]=ch[fail[u]][i];
}
}
}
void dfs(int u)
{
siz[u]=val[u];
for(int i=to[u];i;i=nx[i])
{
dfs(i);
siz[u]+=siz[i];
}
}
void pr()
{
for(int i=1;i<=n;++i)
printf("%d\n",siz[pos[i]]);
}
}
char buf[N];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);
for(int i=1;i<=n;++i)
{
scanf("%s",buf);
AC::ins(buf,strlen(buf),i);
}
AC::getfail();
AC::dfs(0);
AC::pr();
return 0;
}