Oulipo
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 14051 Accepted: 5667
Description
給出兩個字符串W和T，求T中有幾個W子串。
Input www.2cto.com
第一行為數據數.
每組數據有兩行W和T，表示模式串和原始串.
Output
對每組數據，每行一個數，表示匹配數.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
Source
BAPC 2006 Qualification
這題用到了KMP中的覆蓋函數——P
P和Next的區別是P是指包括當前點的最長覆蓋長度，Next是指匹配到i，若不滿足條件，將其挪到Next[i]，(P[i]<>P[next[i]],P表模式串）
證明：
之後進行查找，若查到(j=m),則j=P[j]（為了下一次查找）
[delphi]
Program Poj3461;
const
maxm=10000;
maxn=1000000;
var
tt,n,m,i,j:longint;
a,b:ansistring;
P:array[1..maxn] of longint;
function kmp:longint;
var
n,m,i,j:longint;
begin
kmp:=0;
n:=length(a);m:=length(b);
P[1]:=0;j:=0;
for i:=2 to m do
begin
while (j>0) and (b[j+1]<>b[i]) do j:=p[j];
if (b[j+1]=b[i]) then inc(j);
p[i]:=j;
end;
j:=0;
for i:=1 to n do
begin
while (j>0) and (b[j+1]<>a[i]) do j:=p[j];
if (b[j+1]=a[i]) then inc(j);
if j=m then
begin
inc(kmp);
j:=p[j];
end;
end;
end;
begin
readln(tt);
while (tt>0) do
begin
readln(b);
readln(a);
writeln(kmp);
dec(tt);
end;
end.
