KMP算法

发表于 | 分类于
字数统计: 1,158

为了避免朴素匹配算法需要向左回溯导致效率较低的缺点，引进了无需回溯的KMP算法。

KMP算法

利用模式串P自身的重复模式

关注：

  • 匹配失败，是否发生在P的第一个字符处？
    • 若当前轮匹配在进行第一个字符比较时就失败，那么
      下一轮应该是比较T[i+1]和P[1]
  • P中是否有重复模式？
    • 若P中在当前轮成功匹配的子串的后缀与子串的前缀
      无重复模式，那么下一轮应该是比较T[i]和P[1]
    • 若P中在当前轮成功匹配的子串的后缀与子串的前缀
      有重复模式，那么下一轮应该是比较T[i]和P[next[j]]
    • 模式串的next[j] = ？ next[j]就是第j个元素前j-1个元素首尾重合部分个数加1
      • 规定任何一个串，next[1]=0
      • next[i]= [P串中前 i-1 子串首尾最长匹配数 + 1] —— 首尾重合不包括本身
      • 其他情况，next[i]= 1

匹配过程：若某轮匹配失败，则利用next数组分别计算下一轮匹配时目标串和模式串的开始位置

若是T[i]≠P[j]导致当前轮的匹配失败，则按照下列规则开始下一轮匹配：

  • 若next[j] ≠ 0，则将T[i..]与P[next[j]..]匹配
  • 若next[j]==0，则将T[(i+1)..]与P[1..]匹配

nextval数组

什么情况下有改进的空间？

假设T[i] ≠P[j]导致失配 。若P[j]==P[next[j]]，此时若向右移动模式串P，将T[i]与P[next[j]]对齐进行比较必然是无意义的，因为此时T[i]必定≠P[next[j]]。

如何改进？用nextval数组代替next数组。

  • nextval[1]=0;
  • for(j>1;j<=n;j++)
    若P[j]==P[next[j]]，则nextval[j]=nextval[next[j]];
    若P[j]≠P[next[j]]，则nextval[j]=next[j];
    若某轮匹配失败，则利用nextval数组计算下一轮匹配时的目标串和模式串的开始位置（类似next数组的应用）
  • 一直比到相等为止

KMP算法近似时间复杂度为O(n+m),其中O(n)表示比较的时间， O(m)表示计算next数组的时间.

若每轮中模式串与目标串之间的不匹配都发生在模式串的第一个字符处，则KMP算法会退化到朴素模式匹配算法。 

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;
void get_next(char *t, int *next)
{
	int len = strlen(t + 1);
	int i = 1, j = 0;
	next[i] = j; // 数组第二个元素设为next数组第一个值
	while (i < len)
	{
		if (j == 0 || t[i] == t[j])//j==0是用来设置第二个值；t[i] == t[j] 是比较后缀的单个字符与前缀的单个字符？
		{
			++i;
			++j;
			next[i] = j;
		}
		else
			j = next[j];
	}
	    for(int k=1;k<=len;++k)
	        cout<<next[k]<<" ";
	    cout<<endl;
	return;
}
void get_nextval(char *t, int *nextval)
{
	int i = 1, j = 0;
	nextval[1] = 0;
	int len = strlen(t + 1);
	while (i < len)
	{
		if (j == 0 || t[i] == t[j])
		{
			++i;
			++j;
			if (t[i] != t[j])//若当前字符与前缀字符不相等
				nextval[i] = j;//则当前的j为nextval在i位置的值（即next[i]）
			else//若当前字符与前缀字符相等
				nextval[i] = nextval[j];//则将前缀字符的nextval的值赋值给nextval[i],即nextval[i]=next[next[i]];
		}
		else
			j = nextval[j];
	}
	    for(int k=1;k<=len;k++)
	        cout<<nextval[k]<<" ";
	    cout<<endl;
}

//返回子串t在主串s中第pos个字母后的位置
int kmp_next(char *s, char *t, int pos)
{
	int next[105];
	memset(next, 0, sizeof(next));
	get_next(t, next);
	int i = pos;
	int j = 1;
	int len_s = strlen(s + 1);
	int len_t = strlen(t + 1);
	while (i <= len_s && j <= len_t)
	{
		if (j == 0 || s[i] == t[j])
		{
			++i;
			++j;
		}
		else
			j = next[j];
	}
	if (j > len_t)//表示t串匹配成功
		return i - len_t;
	else
		return 0;
}
int kmp_nextval(char *s, char *t, int pos)
{
	int nextval[105];
	memset(nextval, 0, sizeof(nextval));
	get_nextval(t, nextval);
	int i = pos;
	int j = 1;
	int len_s = strlen(s + 1);
	int len_t = strlen(t + 1);
	while (i <= len_s && j <= len_t)
	{
		if (j == 0 || s[i] == t[j])
		{
			++i;
			++j;
		}
		else
			j = nextval[j];
	}
	if (j > len_t)
		return i - len_t;
	else
		return 0;
}
int main()
{
	char t[105], s[105];
	int pos;
	scanf("%s%s%d", s + 1, t + 1, &pos); // 目标串，模式串，开始查找位置
	printf("%d\n", kmp_next(s, t, pos));
	printf("%d\n", kmp_nextval(s, t, pos));
	system("pause");
	return 0;
}