功能:输入一个原串,再输入N个待匹配串,在待匹配串中找出全部原串的起始位置
原理:KMP算法,其实这个东西已经包含了AC自动机的思想(fail指针/数组),只不过适用于单模板匹配,不过值得一提的是在单模板大量匹配待匹配串时,这个会有相当大的优势,AC自动机虽然好想一些,但是在这一类问题上的性价比就略低了
1 var
2 i,j,k,l,m,n:longint;
3 a:array[0..100000] of longint;
4 s1,s2:ansistring;
5 begin
6 readln(s1);
7 a[1]:=0;
8 for i:=2 to length(s1) do
9 begin
10 j:=a[i-1];
11 while (j>0) and (s1[j+1]<>s1[i]) do j:=a[j];
12 if s1[j+1]=s1[i] then a[i]:=j+1 else a[i]:=0;
13 end;
14 readln(n);
15 for l:=1 to n do
16 begin
17 readln(s2);
18 j:=0;
19 for i:=1 to length(s2) do
20 begin
21 inc(j);
22 if s1[j]=s2[i] then
23 begin
24 if j=length(s1) then
25 begin
26 write(i-length(s1)+1,' ');
27 j:=a[j];
28 end;
29 end
30 else
31 begin
32 j:=j-1;
33 while (j>0) and (s1[j+1]<>s2[i]) do j:=a[j];
34 if s1[j+1]=s2[i] then inc(j) else j:=0;
35 end;
36 end;
37 writeln;
38 end;
39 readln;
40 end.
41