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

- 【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 ...

- 【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 ...

- 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 ...

- 【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 ...

- [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 ...

- 【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 ...

- BZOJ3172&&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 ...

- 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 ...

- 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 ...

- 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

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

- 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 ...

- 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 ...

- 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) ...

- NSString Screening and the last blank 、 Blank line , Wrap more lines into a new line
- (NSString *)filterBlankAndBlankLines:(NSString *)str { NSMutableString *Mstr = [NSMutableString st ...

- 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 ...

- 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) ...

- 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 ...

- 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 ...

- 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 ...