铁丝网

互相联通的梦境

0%

KMP算法学习笔记(2)

发表于 更新于

上一部分在这里

部分匹配表

  • 目的是为了让这个算法对于A中的每个字符都只匹配一次。
  • 对于B中的每一个字符x，查找x’使得B[1..x]中的前x’个字母和后x’个字母完全相等。这样就可以实现直接转移，重新开始匹配的操作。
  • 显然这只和B串有关，因此可以预处理出T[x]表示B[x+1]无法匹配时，最大的x’的值。
  • 对于T[x+1],如果B[T[x]+1]==B[x+1],则T[x+1]=T[x]+1，否则一直后退，知道满足条件为止。
  • 惊奇的发现这也是一个往回跳的过程！

复杂度分析

  • 运用匹配算法是的分析法，可以看出算部分匹配表的复杂度是O(k)的，其中k是B的长度
  • 因此总复杂度是O(n*k)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char A[2000005],B[2000005];
int nxt[2000005];//不能用next，因为是保留字
int main()
{
  scanf("%s%s",A,B);
  nxt[0] = nxt[1] = 0;
  int len1 = strlen(A), len2=strlen(B);
  int k;
  k = 0;
  for (int i = 1; i < len2; i++) //制作部分匹配表
  {
    while(k && B[i] != B[k]) k = nxt[k]; //不停往回跳，直到可以匹配上为止
    if(B[i] == B[k]) nxt[i+1] = ++k; //如果匹配上了
    else nxt[i+1]=0; //否则只能跳到第一个
  }
  k = 0;
  for (int i = 1; i < len1; i++) //开始匹配
  {
    while(k && A[i] != B[k]) k = nxt[k];
    if(A[i] ==  B[k]) k++; //匹配成功了就进行到下一位
    if(k == len2) printf("%d\n", i - len2 + 2); //输出匹配成功的起始位置，因为字符串下标从0开始，所以+2
  }
  for (int i = 1; i<= len2; i++) printf("%d", nxt[i]); //输出nxt数组的值
  return 0;
}

参考资料

终于填掉这个坑！开心！