pku3461 Oulipo

对于每一组数据(b,a)，统计b在a中出现的次数。

一道裸的KMP匹配题，你用BM我也没意见。

View Code

 1 program pku3461(input,output);
 2 var
 3    a,b      : ansistring;
 4    next      : array[0..20000] of longint;
 5    cases  : longint;
 6    i,j,k  : longint;
 7    answer : longint;
 8 begin
 9    readln(cases);
10    for k:=1 to cases do
11    begin
12       readln(b);
13       readln(a);
14       fillchar(next,sizeof(next),0);
15       j:=0;
16       next[1]:=0;
17       for i:=2 to length(b) do
18       begin
19      while (b[j+1]<>b[i])and(j>0) do
20         j:=next[j];
21      if b[j+1]=b[i] then
22         inc(j);
23      next[i]:=j;
24       end;
25       j:=0;
26       answer:=0;
27       for i:=1 to length(a) do
28       begin
29      while (j>0)and(a[i]<>b[j+1]) do
30         j:=next[j];
31      if a[i]=b[j+1] then
32         inc(j);
33      if j=length(b) then
34      begin
35         inc(answer);
36         j:=next[j];
37      end;
38       end;
39       writeln(answer);
40    end;
41 end.