TJOI2013 单词

单词

某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。

给出一个由若干单词组成的单词表,问每个单词在这个表中出现了几次.

jklover的题解

很像一个 kmp 或是 AC 自动机裸题,然而并没有那么简单.用自动机做 n 次匹配,可能会被卡掉.如果一直跳 fail 指针,就可以构造一组数据让你一直跳.

正确的做法是使用 fail 树,连出这样所有的有向边 fail[x]−>x .自动机上,每个节点都代表了一个前缀,连出边后,可以发现父亲节点是儿子节点的后缀.

而一个字符串被匹配的次数恰好等于以它为后缀的前缀数目,即 fail 树中子树的大小.

插入字符串的时候将经过的每个节点的权值 +1 ,最后 dfs 统计即可.

时间复杂度：线性。

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
",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;
}