算法模板——哈希单模板字符串匹配

 1 const pa=314159;pb=951413;
 2 var
 3    i,j,k,l,m,n:longint;
 4    ap,bp:array[0..100000] of int64;
 5    ma,mb,va,vb:int64;
 6    s1,s2,s3:ansistring;
 7 begin
 8      ap[0]:=1;bp[0]:=1;
 9      for i:=1 to 100000 do
10          begin
11               ap[i]:=(ap[i-1]*pa) mod pb;
12               bp[i]:=(bp[i-1]*pb) mod pa;
13          end;
14      readln(s1);
15      ma:=0;mb:=0;
16      for i:=1 to length(s1) do
17          begin
18               ma:=(ma+ord(s1[i])*ap[i]) mod pb;
19               mb:=(mb+ord(s1[i])*bp[i]) mod pa;
20          end;
21      readln(n);
22      for j:=1 to n do
23          begin
24               readln(s2);
25               if length(s2)<length(s1) then continue;
26               va:=0;vb:=0;
27               for i:=0 to length(s1)-1 do
28                   begin
29                        va:=(va+ord(s2[i])*ap[i]) mod pb;
30                        vb:=(vb+ord(s2[i])*bp[i]) mod pa;
31                   end;
32               for i:=length(s1) to length(s2) do
33                   begin
34                        va:=(va-ord(s2[i-length(s1)])*ap[i-length(s1)]+ord(s2[i])*ap[i]) mod pb;
35                        va:=(va+(abs(va) div pb+1)*pb) mod pb;
36                        vb:=(vb-ord(s2[i-length(s1)])*bp[i-length(s1)]+ord(s2[i])*bp[i]) mod pa;
37                        vb:=(vb+(abs(vb) div pa+1)*pa) mod pa;
38                        if (((ma*ap[i-length(s1)]) mod pb)=va) and (((mb*bp[i-length(s1)]) mod pa)=vb) then write(i-length(s1)+1,' ');
39                   end;
40               writeln;
41          end;
42 end.