menu Home Tags Archives Video About
字符匹配_KMP算法

一言加载中...

什么是KMP算法

通俗的讲:从一个字符串中找到包含第二个字符串的开始位置。如果存在返回索引位置,否则返回-1。

问题介绍:

实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

示例:

1
2
3
4
5
6
//下面解题思路以此为例
输入: haystack = "abacaabacabac", needle = "abacab"
输出:5

输入: haystack = "aaaaa", needle = "bba"
输出: -1

来源:力扣(LeetCode))

KMP算法思路

先看个动态图

首先制作一个前缀表(PrefixTable)

前缀表的构建对于KMP算法很重要,后面会说到作用,以及如何生成。

needle 字符串的前缀表如下:

子串排列 最大公共子串 最大公共子串数
a 0
ab 0
aba a 1
abac 0
abaca a 1
abacab ab 2
索引(i) 0 1 2 3 4 5
字符 a b a c a b
prefix[i] 0 0 1 0 1 2

将Prefix表所有数值后移一位,第一个值补为-1,如下:
|索引(i)|0|1|2|3|4|5|
|—|—|—|—|—|—|—|
|字符|a|b|a|c|a|b|
|prefix[i]|-1|0|0|1|0|1|

KMP匹配思想:

  1. 开始匹配,刚开始i=0,j=0,needle[j]与haystack[i]进行比较,直到i=5时,needle[5]与haystack[5]不相等,此时将i指向索引为prefix[5]的位置。
  2. 此时发现prefix[5]之前是匹配成功的,不用管,直接从索引为prefix[5]的位置继续往后比较,直到如图a->b匹配失败,就回到prefix[1]的位置
  3. 当出现prefix的值为-1时,那么i,j同时往后移动一位,继续上面的操作。
  4. 当i的值小于等于(origin.Length - pattern.Length)时跳出上面的循环。

完整过程

那么如何生成prefix表?

qaq 自己明白容易,讲出来挺难额…

代码实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
static int KMP(string origin,string pattern)
{
if (origin.Length < pattern.Length) return -1;
else if (pattern.Length == 0) return 0;
else if (origin == pattern) return 0;

int[] prefix = new int[pattern.Length];

//初始化Prefix表
int pivit = 0;
for (int i = 1; i < pattern.Length; i++)
{
if (pattern[pivit] == pattern[i])
{
++pivit;
prefix[i] = pivit;
}
else
{
pivit = 0;
prefix[i]=0;
}
}

//prefix 数据后移一位,prefix[0] = -1
for (int i = prefix.Length - 1; i > 0; i--)
prefix[i] = prefix[i - 1];
prefix[0] = -1;

//KMP查找
int index = 0;
int jndex = 0;
while (index <= origin.Length - pattern.Length)
{
if (jndex == pattern.Length-1)
return index = jndex;
if (origin[index] == pattern[jndex] || prefix[index]==-1)
{
++index;
++jndex;
}
else
{
jndex = prefix[jndex];
}
}
return -1;
}

参考

评论