bzoj3172【TJOI2013】單詞

Description

某人讀論文，一篇論文是由許多單詞組成。但他發現一個單詞會在論文中出現很多次，現在想知道每個單詞分別在論文中出現多少次。

Input

第一個一個整數N,表示有多少個單詞，接下來N行每行一個單詞。每個單詞由小寫字母組成，N<=200,單詞長度不超過10^6

Output

輸出N個整數，第i行的數字表示第i個單詞在文章中出現了多少次。

Sample Input

Sample Output

HINT

Source

AC自動機+遞推，思路很好（詳見程序）

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 1000005
#define inf 1000000000
using namespace std;
int n,tot=1,cnt=0,t[maxn][26],go[maxn],w[maxn],a[maxn],p[205];
bool v[maxn];
char s[maxn];
queue q;
inline void bfs()
{
	q.push(1);
	while (!q.empty())
	{
		int x=q.front(),y,j;q.pop();v[x]|=v[go[x]];
		a[++cnt]=x;//a數組是按bfs順序生成的 
		F(i,0,25)
		{
			j=go[x];
			while (j&&!t[j][i]) j=go[j];
			if (t[x][i])
			{
				go[y=t[x][i]]=j?t[j][i]:1;
				q.push(y);
			}
			else t[x][i]=j?t[j][i]:1;
		}
	}
}
int main()
{
	scanf("%d",&n);
	F(i,1,n)
	{
		scanf("%s",s);
		int len=strlen(s),now=1;
		F(j,0,len-1)
		{
			int x=s[j]-'a';
			if (!t[now][x]) t[now][x]=++tot;
			now=t[now][x];
			w[now]++;
		}
		p[i]=now;//p數組記錄了每個單詞結尾節點的位置 
	}
	bfs();
	D(i,cnt,1) w[go[a[i]]]+=w[a[i]];//這裡計算答案的方法很巧妙，相當於按bfs的反方向遞推 
	F(i,1,n) printf("%d\n",w[p[i]]);//這裡只要輸出w[p[i]]就可以了 
	return 0;
}