单词
https://loj.ac/problem/10060
题目描述
给出若干单词，要求求出每个单词在文章（文章由这些单词构成）中的出现次数。
思路
题意有一点毒瘤，不过这道题显然需要用\(AC\)自动机，我们要解决的就是如何维护每个单词的出现次数。这里我们需要用到\(fail\)树统计答案。我们考虑对\(fail\)数组所建成的图，显然它的根节点为\(0\)，并且每个节点只有一条出边。所以我们所以我们每个单词的答案就是\(fail\)树中其子树的权值和，权值即为经过次数。
对\(fail\)树的处理可以有两种：
\(①\)像我一样，没有发现\(bfs\)找\(next\)数组时规律，直接暴力重新建树，\(dfs\)求子树和。
\(②\)我们考虑\(bfs\)搜索时队列中的深度依次增大，而\(next[v]\)的深度一定小于\(v\)，所以可以倒着把队列中的数处理一遍即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int ch[MAXN][26],siz[MAXN],fail[MAXN],ed[MAXN],tot;
char s[MAXN];
int nxt[MAXN],head[MAXN],to[MAXN],sum;
void add_edge(int x,int y)
{
nxt[++sum]=head[x];
head[x]=sum;
to[sum]=y;
}
void clear()
{
memset(ch,0,sizeof(ch));
memset(siz,0,sizeof(siz));
memset(head,-1,sizeof(head));
tot=1;sum=0;
for(int i=0;i<26;i++)
ch[0][i]=1,ch[1][i]=0;
}
void insert(char *s,int x)
{
int u=1,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
if(!ch[u][c])ch[u][c]=++tot;
u=ch[u][c];
siz[u]++;
}
ed[x]=u;
}
void bfs()
{
queue<int>q;
q.push(1);fail[1]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;i++)
{
if(!ch[u][i])ch[u][i]=ch[fail[u]][i];
else
{
int v=fail[u];
while(v>0&&!ch[v][i])v=fail[v];
q.push(ch[u][i]);
fail[ch[u][i]]=ch[v][i];
}
}
}
}
void dfs(int u,int fa)
{
for(int i=head[u];~i;i=nxt[i])
{
int v=to[i];
if(v==fa)continue ;
dfs(v,u);
siz[u]+=siz[v];
}
}
int main()
{
int n;
clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf(" %s",s);
insert(s,i);
}
bfs();
for(int i=1;i<=tot;i++)
add_edge(fail[i],i);
dfs(1,0);
for(int i=1;i<=n;i++)
printf("%d\n",siz[ed[i]]);
return 0;
}1、深拷贝和浅拷贝
2、[转]IBM ThinkPad 全新、原装机验机流程（完全版）
3、个人博客作业week7
4、jQuery 焦点图,图像文件js档
5、C面试题汇总(转)