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

Posted on by
内容目录
Language:
Oulipo
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 14051   Accepted: 5667

Description

给出两个字符串W和T，求T中有几个W子串。

Input

第一行为数据数.

每组数据有两行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]（为了下一次查找）


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.