3172: [Tjoi2013]单词

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 4731  Solved: 2314
[Submit][Status][Discuss]

Description

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

Input

第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N<=200,单词长度不超过10^6

Output

输出N个整数,第i行的数字表示第i个单词在文章中出现了多少次。

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

HINT

Source

【题解】

板子题……注意两个字符串相等的情况。

/********************************************

	Title		BZOJ3172.cpp
	Author 		TomatoLoveCoconut
	Time		2018-4-01
	History		Created 2018-4-01
	
	Version		1.0.0
	
	Tags:


	while(true) RP++;
	
		 QAQ

*********************************************/


#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define base 311
#define mod 19270817
#define maxlongint 2147483647
#define maxint 32767
#define pi (double)acos(-1.0)
#define eps 1e-9
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
//SGT
#define MID ((l+r)>>1)
#define lson (o<<1)
#define rson (o<<1|1)
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a));
#define clc(a) memset(a,-1,sizeof(a));
#define maxn 1000100


using namespace std;


//complex
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
};
inline Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
inline Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
inline Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x);}
//BIT
inline int lowbit(int x){return x&(-x);}




//var
int ch[maxn][26],val[maxn],f[maxn],last[maxn];
int ans[210];
char S[210][maxn];
vector<int> G[210];
int cnt=0;
int C=0;
struct Ac_automaton{
	inline int idx(char c)
	{
		return c-'a';
	}
	inline void insert(char *s,int v)
	{
		int n=strlen(s);
		int u=0;
		for (int i=0;i<n;i++)
		{
			int c=idx(s[i]);
			if (!ch[u][c])
			{
				ch[u][c]=++cnt;
				memset(ch[cnt],0,sizeof(ch[cnt]));
			}
			u=ch[u][c];
		}
		val[u]=v;
	}
	inline void getFail()
	{
		queue<int> Q;
		cla(f);
		for (int i=0;i<26;i++)
		{
			if (ch[0][i]!=0)
				Q.push(ch[0][i]);
		}
		while (!Q.empty())
		{
			int u=Q.front();
			Q.pop();
			for (int c=0;c<26;c++)
			{
				int v=ch[u][c];
				if (!v)
					continue;
				Q.push(v);
				int r=f[u];
				while (r && !ch[r][c]) r=f[r];
				f[v]=ch[r][c];
				last[v]=val[f[v]]?f[v]:last[f[v]];
			}
		}
	}
	inline void print(int j)
	{
		if (j)
		{
			if (val[j])
			{
				ans[val[j]]++;	
			for (int i=0;i<G[val[j]].size();i++)
				ans[G[val[j]][i]]++;
			}
			print(last[j]);
		}
	}
	inline void find(char *T)
	{	
		int n=strlen(T);
		int j=0;
		for (int i=0;i<n;i++)
		{
			int c=idx(T[i]);
			while (j && !ch[j][c]) j=f[j];
			j=ch[j][c];
			if (val[j])	print(j);
			else	if (last[j])
				print(last[j]);
		}
	}
}Trie;



int n;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{	
		scanf("%s",S[i]);
		Trie.insert(S[i],i);
	}
	for (int i=1;i<n;i++)
	{
		int N=strlen(S[i]);
		for (int j=i+1;j<=n;j++)
		 {
		 	int M=strlen(S[j]);
		 	bool flag=true;
			if (N==M)
				for (int k=0;k<N;k++){
					if (S[i][k]!=S[j][k]){flag=false;break;}
			}else  continue;
			if (flag)
			{
				G[i].push_back(j);
				G[j].push_back(i);
			}
		}
	}
	Trie.getFail();
	for (int i=1;i<=n;i++)
	{
		Trie.find(S[i]);
	}
	for (int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}













/****************************************************
		Any Questions Please Contact Me
		Tencent QQ:	898021802
		Website:	primopan.org
		Email:		primojpan@gmail.com
****************************************************/

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注