首页 > 代码库 > 3172: [Tjoi2013]单词
3172: [Tjoi2013]单词
3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1424 Solved: 653
[Submit][Status]
Description
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
Output
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
3
a
aa
aaa
a
aa
aaa
Sample Output
6
3
1
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 do10 begin11 c[i]:=x+1;12 p:=0;13 while not(eoln) do14 begin15 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 do26 begin27 a[1]:=0;28 k:=0;29 for j:=1 to d[i]-1 do30 begin31 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 do38 begin39 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] then42 begin43 inc(y);44 k:=a[k];45 end;46 end;47 writeln(y);48 end;49 end.
3172: [Tjoi2013]单词
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。