实现功能:第一行输入模板串;第二行输入N;接下来N行每行一个字符串,将每个字符串中出现的模板串的起始位置找出
原理:字符串双值哈希啦啦啦,和KMP其实差不太多,但是字符串双值哈希绝对是个字符串题乱搞神器!!!
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.