POJ 3461(模式匹配数&覆盖函数）

Oulipo
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 14051 Accepted: 5667
Description
给出两个字符串W和T，求T中有几个W子串。
Input www.zzzyk.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.

补充：软件开发 , C++ ,