实现功能——输入N,M,提供一个共计N个单词的词典,然后在最后输入的M个字符串中进行多串匹配(关于AC自动机算法,此处不再赘述,详见:Aho-Corasick 多模式匹配算法、AC自动机详解。考虑到有时候字典会相当稀疏,所以引入了chi和bro指针进行优化——其原理比较类似于邻接表,这个东西和next数组本质上是一致的,只是chi和bro用于遍历某一节点下的子节点,next用于查询某节点下是否有需要的子节点)
1 type
2 point=^node;
3 node=record
4 ex:longint;st:ansistring;
5 ct:char;
6 fat,jump,chi,bro:point;
7 next:array['A'..'Z'] of point;
8 end;
9 var
10 i,j,k,l,m,n:longint;
11 head,p:point;
12 s1,s2:ansistring;
13 function getpoint:point;inline;
14 var p:point;c1:char;
15 begin
16 new(p);
17 p^.ex:=0;p^.st:='';
18 p^.ct:=chr(0);
19 p^.bro:=nil;p^.chi:=nil;
20 p^.fat:=nil;p^.jump:=head;
21 for c1:='A' to 'Z' do p^.next[c1]:=nil;
22 exit(p);
23 end;
24 procedure ins(s1:ansistring;x:longint);inline;
25 var p:point;s2:ansistring;i:longint;
26 begin
27 p:=head;S2:='';
28 for i:=1 to length(s1) do
29 begin
30 s2:=s2+s1[i];
31 if p^.next[s1[i]]=nil then
32 begin
33 p^.next[s1[i]]:=getpoint;
34 p^.next[s1[i]]^.fat:=p;
35 p^.next[s1[i]]^.st:=s2;
36 p^.next[s1[i]]^.ct:=s1[i];
37 p^.next[s1[i]]^.bro:=p^.chi;
38 p^.chi:=p^.next[s1[i]];
39 end;
40 p:=p^.next[s1[i]];
41 end;
42 if p^.ex=0 then p^.ex:=x;
43 end;
44 procedure linkit;inline;
45 var i,j,k,l,f,r:longint;
46 d:array[0..10000] of point;
47 p,p1,p2:point;
48 begin
49 f:=1;r:=2;d[1]:=head;
50 while f<r do
51 begin
52 p:=d[f]^.chi;
53 while p<>nil do
54 begin
55 d[r]:=p;
56 if d[f]<>head then
57 begin
58 p1:=d[f]^.jump;
59 while p1<>head do
60 begin
61 if p1^.next[p^.ct]<>nil then break;
62 p1:=p1^.jump;
63 end;
64 if p1^.next[p^.ct]<>nil then p^.jump:=p1^.next[p^.ct];
65 end;
66 inc(r);
67 p:=p^.bro;
68 end;
69 inc(f);
70 end;
71 end;
72 procedure fit(s1:ansistring);inline;
73 var p,p1:point;i:longint;
74 begin
75 p:=head;
76 for i:=1 to length(s1) do
77 begin
78 if p^.next[s1[i]]=nil then
79 begin
80 while (p^.next[s1[i]]=nil) and (p<>head) do p:=p^.jump;
81 if p^.next[s1[i]]<>nil then p:=p^.next[s1[i]];
82 end
83 else p:=p^.next[s1[i]];
84 p1:=p;
85 while p1<>head do
86 begin
87 if p1^.ex<>0 then writeln('No.',p1^.ex,' ',p1^.st,' From:',i-length(p1^.st)+1);
88 p1:=p1^.jump;
89 end;
90 end;
91 end;
92 begin
93 readln(n,m);
94 head:=getpoint;head^.jump:=head;
95 for i:=1 to n do
96 begin
97 readln(s1);
98 ins(upcase(s1),i);
99 end;
100 linkit;
101 for i:=1 to m do
102 begin
103 readln(s1);
104 fit(upcase(s1));
105 end;
106 end.
107