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

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-15

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.