题解 [TJOI2013] 单词

题意

题面：传送门

就是给 \(n\)个单词，询问对于每个单词出现过多少次。

Solution

一道AC自动机的板子题，加深一下理解。

首先注意一点：不能把题目中给的所有单词全部并起来，因为这可能会使得前一个单词的后缀与后一个单词的前缀合并成新的单词。

其实只要在每个单词之间添加一个奇怪的符号就可以了。

然后就很好做了。

数据范围\(1e6\),如果暴力跳\(fail\)的话会导致很多节点的重复经过。可以用一个计数器统计一下每个节点的访问次数。

将\(fail\)指针全部反过来，因为跳 \(fail\)的时候一定是跳向不深于当前位置的节点，且每个节点仅指向\(1\)个节点。所以将\(fail\)指针反过来就变成了一棵树。我们在树上统计答案。

一个节点被访问（也就是匹配）的次数在树上显然是它的子树和，因为有且仅有它子树中的节点会通过\(fail\)指针访问到它。

建立 \(trie\)树的时候标记一下每个字符串的终止节点编号，输出对应的\(cnt\)即可。

#include
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
using namespace std;
typedef long long ll;
template  inline void read(T &x){
	ll f = 1;x = 0;char ch = getchar();
	while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}
	while (isdigit(ch)){x = (x << 1)+(x << 3)+(ch ^ 48);ch = getchar();}
	x *= f;
}

const int MAXL=2001000;
const int MAXN=1000010;

int cnt[MAXN],fail[MAXN],n,siz;
int trie[MAXL][26],end[MAXL],tot;
vector edge[MAXN];
char text[MAXL];

inline void Add(char *st)
{
	int len=strlen(st);
	rep(i,0,len-1)text[siz++]=st[i];
	text[siz++]='&';
}

inline void insert(char *st,int id)
{
	int pos=0,len=strlen(st);
	rep(i,0,len-1)
	{
		int ch=st[i]-'a';
		if(!trie[pos][ch])trie[pos][ch]=++tot;
		pos=trie[pos][ch];
	}
	end[id]=pos;
}

inline void Getfail()
{
	queue Q;
	rep(i,0,25)if(trie[0][i])Q.push(trie[0][i]);
	
	while(!Q.empty())
	{
		int x=Q.front();
		Q.pop();
		rep(i,0,25)
		{
			if(trie[x][i])
			{
				fail[trie[x][i]]=trie[fail[x]][i];
				Q.push(trie[x][i]);
			}else
			{
				trie[x][i]=trie[fail[x]][i];
			}
		}
	}
}

inline void dfs(int pos)
{
	int len=edge[pos].size();
	rep(i,0,len-1)
	{
		int to=edge[pos][i];
		dfs(to);
		cnt[pos]+=cnt[to];	
	} 
}

inline void solve()
{
	int pos=0;
	int len=strlen(text);
	rep(i,0,len-1)
	{
		int ch=text[i]-'a';
		pos=trie[pos][ch];
		++cnt[pos];
	}
	
	rep(i,1,tot)edge[fail[i]].push_back(i);
	
	dfs(0);
	
	rep(i,1,n)printf("%d\n",cnt[end[i]]);
}

int main()
{
	scanf("%d",&n);
	
	rep(i,1,n)
	{
		char ss[MAXN];
		scanf("%s",ss);
		Add(ss);
		insert(ss,i);
	}
	Getfail();
	solve(); 
	return 0;
}

`