算法介绍：

KMP是一种用来处理字符串匹配问题的算法，给你两个字符串A、B，让你回答B是否为A的子串，或者A中有多少子串等于B。

这题最暴力的做法是：枚举A中与B相等的子串的左端点，再判断是否与B相等，时间复杂度是O(nm)的，很慢。而我们要介绍的KMP算法的时间复杂度是理论上O(n+m)的，比他要快得多。

算法核心思路分析：

KMP算法其实是这么做的：两个指针，i，j，表示A中从i-j+1到i的这段子串与B的1到j完全相等。当A[i+1]=B[j+1]时显然两个指针都自增1即可。那么当A[i+1]<>B[j+1]时呢？我们就需要重新匹配j指针，找到能够与指针i+1相匹配的新也要是最大的的指针j，使得以上关系仍然成立（注意是重新匹配指针j，而i始终按照自己的进程不断地+1）。而我们应该如何重新匹配指针j呢？注意到字符串B中，会有子串1-x，为1-j的子串，而如果有A[i+1]<>B[j+1]但是A[i+1]=B[x+1]的话，我们便不用直接将指针j清零，只需要把j赋为x即可。

代码：

var

  p:array[0..1000]of longint;

  a,b:string;

  i,j,lena,lenb,ans:longint;

begin

  readln(a);

  readln(b);

  lena:=length(a); lenb:=length(b);

  p[1]:=0; j:=0;

  for i:=1 to lenb-1 do

  begin

    while (j>0)and(b[j+1]<>b[i+1]) do j:=p[j];

    if b[j+1]=b[i+1] then inc(j);

    p[i+1]:=j;

  end;

  j:=0;

  for i:=0 to lena-1 do

  begin

    while (j>0)and(a[i+1]<>b[j+1]) do j:=p[j];

    if b[j+1]=a[i+1] then inc(j);

    if j=lenb then

    begin

      inc(ans);

      j:=p[j];

    end;

  end;

  writeln(ans);

end.

巴特西

[KMP]字符串匹配算法

算法介绍：

算法核心思路分析：

代码：

最新文章

热门文章