3172: [Tjoi2013]单词
3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 1424 Solved: 653
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
题解：这个比较明显可以AC自动机乱搞搞，但我还是想到了NOI2014的动物园那题神奇的KMP，于是类比那个来了一发，别的没了（其实简单的kmp在某些方面感觉似乎比AC自动机还要灵活呢。。。真的^_^）
1 var
2 i,j,k,l,m,n,x,p,y:longint;
3 s:array [0..2000010] of char;
4 a,c,d:array [0..2000010] of longint;
5 b:array [0..201,0..200010] of char;
6 begin
7 readln(n);
8 x:=0;
9 for i:=1 to n do
10 begin
11 c[i]:=x+1;
12 p:=0;
13 while not(eoln) do
14 begin
15 inc(x);
16 read(s[x]);
17 inc(p);
18 b[i,p]:=s[x];
19 end;
20 d[i]:=p;
21 inc(x);
22 s[x]:=' ';
23 readln;
24 end;
25 for i:=1 to n do
26 begin
27 a[1]:=0;
28 k:=0;
29 for j:=1 to d[i]-1 do
30 begin
31 while (k>0) and (b[i,k+1]<>b[i,j+1]) do k:=a[k];
32 if b[i,k+1]=b[i,j+1] then inc(k);
33 a[j+1]:=k;
34 end;
35 y:=0;
36 k:=0;
37 for j:=1 to x do
38 begin
39 while (k>0) and (b[i,k+1]<>s[j]) do k:=a[k];
40 if b[i,k+1]=s[j] then inc(k);
41 if k=d[i] then
42 begin
43 inc(y);
44 k:=a[k];
45 end;
46 end;
47 writeln(y);
48 end;
49 end.本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2015-01-31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
