Study here AC automata
In fact the KMP and trie It's easy to expand into AC Automata
Here we use a property
A tree can be built by reversing the mismatch pointer fail Trees
x String in y The number of occurrences in the string is in fail On the tree with x How many nodes in the subtree whose end node is the root belong to y strand , That makes sense
And to this question , The number of times it appears in the article is the size of the subtree whose root is the node at the end of the word
Notice that this question has the same word
I used to do this problem with suffix array O(LlogL)
And the complexity of automata is O(L), Much faster.

 type node=record
po,next:longint;
end; var e:array[..] of node;
trie:array[..,'a'..'z'] of longint;
q,f,p,w:array[..] of longint;
v:array[..] of longint;
t,i,j,k,n,l,len:longint;
s:ansistring; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure bfs;
var x,y,h,r,j:longint;
c:char;
begin
h:=;
r:=;
for c:='a' to 'z' do
if trie[,c]> then
begin
add(,trie[,c]);
inc(r);
q[r]:=trie[,c];
end; while h<=r do
begin
x:=q[h];
for c:='a' to 'z' do
if trie[x,c]> then
begin
y:=trie[x,c];
inc(r);
q[r]:=y;
j:=f[x];
while (j>) and (trie[j,c]=) do j:=f[j];
f[y]:=trie[j,c];
add(trie[j,c],y);
end;
inc(h);
end;
end; procedure dfs(x:longint);
var i,y:longint;
begin
i:=p[x];
while i<> do
begin
y:=e[i].po;
dfs(y);
w[x]:=w[y]+w[x];
i:=e[i].next;
end;
end; begin
readln(n);
for i:= to n do
begin
readln(s);
j:=;
l:=length(s);
for k:= to l do
begin
if trie[j,s[k]]= then
begin
inc(t);
trie[j,s[k]]:=t;
end;
j:=trie[j,s[k]];
inc(w[j]);
end;
v[i]:=j;
end;
bfs;
dfs();
for i:= to n do
writeln(w[v[i]]);
end.

ac automata

 var h,rank,x,y,sum,sa:array[..] of longint;
f:array[..,..] of longint;
where,len,d:array[..] of longint;
now, k,ans,i,j,p,n,m,t,l,r:longint;
s,cc:ansistring;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function lcp(a,b:longint):longint;
var k:longint;
begin
k:=trunc(ln(b-a+)/ln());
exit(min(f[a,k],f[b-d[k]+,k]));
end; begin
readln(t);
for i:= to t do
begin
readln(cc);
where[i]:=length(s)+;
len[i]:=length(cc);
s:=s+cc;
if i<>t then s:=s+' ';
end;
{ for i:=1 to t do
writeln(where[i],' ',len[i]);}
n:=length(s);
for i:= to n do
begin
y[i]:=ord(s[i]);
inc(sum[y[i]]);
end;
m:=;
for i:= to do
inc(sum[i],sum[i-]);
for i:= to n do
begin
sa[sum[y[i]]]:=i;
dec(sum[y[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if y[sa[i]]<>y[sa[i-]] then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=;
while m<n do
begin
y:=rank;
fillchar(sum,sizeof(sum),);
p:=;
for i:=n-j+ to n do
begin
inc(p);
x[p]:=i;
end;
for i:= to n do
if sa[i]>j then
begin
inc(p);
x[p]:=sa[i]-j;
end;
for i:= to n do
begin
rank[i]:=y[x[i]];
inc(sum[rank[i]]);
end;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[rank[i]]]:=x[i];
dec(sum[rank[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if (y[sa[i]]<>y[sa[i-]]) or (y[sa[i]+j]<>y[sa[i-]+j]) then inc(p);
rank[sa[i]]:=p;
end;
j:=j shl ;
m:=p;
end;
h[]:=;
p:=;
for i:= to n do
begin
if rank[i]= then continue;
j:=sa[rank[i]-];
while s[i+p]=s[j+p] do inc(p);
h[rank[i]]:=p;
if p> then dec(p);
end;
k:=trunc(ln(n)/ln());
d[]:=;
for i:= to k do
d[i]:=d[i-]*;
for i:= to n do
f[i,]:=h[i];
for j:= to k do
for i:= to n do
if i+d[j]-<=n then
begin
f[i,j]:=min(f[i,j-],f[i+d[j-],j-]);
end
else break;
for i:= to t do
begin
ans:=;
k:=-;
l:=;
now:=rank[where[i]];
r:=now-;
while l<=r do
begin
m:=(l+r) shr ;
if lcp(m+,now)>=len[i] then
begin
k:=m;
r:=m-
end
else l:=m+;
end;
if k<>- then ans:=ans+now-k;
l:=now+;
k:=-;
r:=n;
while l<=r do
begin
m:=(l+r) shr ;
if lcp(now+,m)>=len[i] then
begin
k:=m;
l:=m+;
end
else r:=m-;
end;
if k<>- then ans:=ans+k-now;
writeln(ans);
end;
end.

The suffix array

bzoj3172 More articles about

  1. 【BZOJ3172】[Tjoi2013] word AC automata

    [BZOJ3172][Tjoi2013] word Description Someone reads a paper , A paper is made up of many words . But he found that a word would appear many times in a paper , Now I want to know how many times each word appears in the paper . Input ...

  2. 【BZOJ3172】 word (AC automata )

    [BZOJ3172] word (AC automata ) Topic Description Someone reads a paper , A paper is made up of many words . But he found that a word would appear many times in a paper , Now I want to know how many times each word appears in the paper . Input ...

  3. BZOJ3172 [Tjoi2013] word character string SA ST surface

    Link to the original text http://www.cnblogs.com/zhouzhendong/p/9026543.html Subject portal - BZOJ3172 The question Input $n(n\leq 200)$ A string , Guarantee the length ...

  4. 【bzoj3172】 Tjoi2013— word

    http://www.lydsy.com/JudgeOnline/problem.php?id=3172 ( Topic link ) The question $n$ Words make up the text , Ask how many times each word appears in the text . Solution topic ...

  5. [BZOJ3172] word

    3172: [Tjoi2013] word Time Limit: 10 Sec  Memory Limit: 512 MB Description Someone reads a paper , A paper is made up of many words . But he found that a word would ...

  6. 【bzoj3172】: [Tjoi2013] word character string -AC automata

    [bzoj3172]: [Tjoi2013] word First, construct one with all the words AC automata The title requires each word in this AC The number of matches in an automaton Every time insert A word on the path cnt++ So a little p-&g ...

  7. BZOJ3172&amp;&amp;lg3966 TJOI word ( Generalized suffix automata )

    BZOJ3172&&lg3966 TJOI word ( Generalized suffix automata ) Topic Find it yourself HINT Give multiple text strings , Let you find how many times each text string appears , Generalized suffix automata build parent tree ...

  8. BZOJ3172: [Tjoi2013] word

    Portal After doing so many questions, how can we still not understand them well AC What about automata .. It's really a staff maker First of all, the meaning of the title is not very clear , All these words make up that article , So make a decision to build AC automata , Add a weight to each point when building , Building a tree is a process of weight, that is ...

  9. BZOJ3172——[Tjoi2013] word

    1. The main idea of the topic : A paper is made up of many words , Now I want to know how many times each word appears in the paper . 2. analysis : Facing Look at the graph of generalized suffix automata , We'll find the mystery , The answer is the number of suffixes under this word ? So we build automata , Then seek ...

  10. BZOJ3172[Tjoi2013] word Answer key

    The main idea of the topic : Find the number of times some strings appear in an article . Ideas : AC The classic application of automata , After building the automaton, you can call the elements in the queue directly Fail Pointer record is enough . Code : #include<cstdio> #inclu ...

Random recommendation

  1. hdu-1213-How Many Tables

    How Many Tables Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)T ...

  2. jauery Join the project , But the page shows that the file was not found --springMVC frame

    There's something very unpleasant , I have already put jquery In the project , But there's always no effect on the page , Developer mode prompt no file found , I was so depressed and crazy at that time , And then I came across Eclipse A reported mistake , How to deal with Spring ...

  3. C Heap and stack in language 20160604

    First of all, the statement here is C Heap and stack in language , It's not in the data structure ! One . Introduction :C Language programs are compiled and connected to form compilers . The binary image file formed after connection is a static region, which consists of code segment and data segment ( It's made up of two parts : Read only data paragraph , Uninitialized number ...

  4. POJ2115 C Looooops( number theory )

    Topic link . analysis : We don't know much about number theory , When it comes to solving , I'm in a lot of trouble . Set the answer to x,n = (1<<k), be (A+C*x) % n == B namely (A+C*x) ≡ B (mod n) ...

  5. NSString Screening and the last blank 、 Blank line , Wrap more lines into a new line

    - (NSString *)filterBlankAndBlankLines:(NSString *)str { NSMutableString *Mstr = [NSMutableString st ...

  6. Use one SQL Sentence take out the second m To the first article n The method of recording

    original text : Use one SQL Sentence take out the second m To the first article n The method of recording   -- from Table  Take the second from the table  m  To the first article  n  A record of :(Not In  edition )       *    FROM Table     id ...

  7. About jquery Of $each((Object, function(p1, p2) usage

    Through it , You can traverse objects . Array and process it . Instructions each The effect of function implementation based on the type of parameter is not completely consistent : 1. Traversing objects ( There are additional parameters ) $.each(Object, function(p1, p2) ...

  8. Makefile Example introduction

    Makefile The rules target ... :prerequisites... command target It's an object file , It can be object file, It can also be an executable file , It can also be a label pr ...

  9. Spring Factory method (factory-bean) To configure bean

    stay spring In the world of , We usually make use of bean config file perhaps annotation Annotate the configuration bean. In the first use bean config file(spring xml) In the way ...

  10. The last scholar's notes --SSHD Services and SCP usage

    sshd Service explanation 1.SSHD service Introduce :SSH  agreement : Secure Shell Protocol . by  Secure Shell  Abbreviation .SSH  For security protocols based on application layer and transport layer . Default port 22 effect : sshd Service usage SS ...