F.A.Qs | Home | Discuss | ProblemSet | Status | Ranklist | Contest | ModifyUser hyxzc | Logout | 捐赠本站 |
---|
Notice:由于本OJ建立在Linux平台下,而许多题的数据在Windows下制作,请注意输入、输出语句及数据类型及范围,避免无谓的RE出现。
3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 2218 Solved: 1033
[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
题解:
只是裸题而已…..
初步使用结构体算法。。。
hzwer伴我成长
代码:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm> using namespace std; int n,pos[];
struct acm
{
int sz,point[],q[],sum[],a[][];
char ch[];
acm()
{sz=;for (int i=;i<=;i++) a[][i]=;} void insert(int &pos)
{
scanf("%s",ch);
int now=;
for (int i=;i<strlen(ch);i++)
{
int t=ch[i]-'a'+;
if (a[now][t]) now=a[now][t];
else now=a[now][t]=++sz;
sum[now]++;
}
pos=now;
} void acmach()
{
int w=,t=;
point[]=,q[]=;
while (t<w)
{
int now=q[t++];
for (int i=;i<=;i++)
{
if (!a[now][i]) continue;
int k=point[now];
while (!a[k][i])k=point[k];
point[a[now][i]]=a[k][i];
q[w++]=a[now][i];
}
}
for (int i=t-;i>=;i--)
{
sum[point[q[i]]]+=sum[q[i]];
}
} }acm; int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
acm.insert(pos[i]);
acm.acmach();
for (int i=;i<=n;i++)
printf("%d\n",acm.sum[pos[i]]);
}