字符串的模式匹配

发表于 | 分类于 | |
字数统计: 1,350 | 阅读时长 ≈ 6

引论

这里主要想讨论一下字符串的模式匹配，主要是KMP算法。

假设我们有一个字符串S，称之为原始串；另一个字符串T，称之为模式串；字符串匹配是指找出原始串S中是否含有模式串T，如果含有，则返回S中第一个匹配项的位置；

例如S = a b c a b c a b d e f；T = a b c a b d；那么我们可以得到S 中含有模式串T，我们返回S中第一个匹配项的位置，即3。

Brute-Force算法

暴力算法，应该算是最朴素的算法了，大概小学生也能想出这个解决方法；BF算法的思想是：从S的第一个字符与T的第一个字符开始比较，如果相等，则进行下一个字符的比较，直到遇到不相等的项；这时我们把T的第一个字符与S的第二个字符相比较，重复上面的过程，知道找到匹配的项为止，或者返回一个值，显示没有匹配的项。

对上面的例子：

a b c a b c a b d e f

a b c a b d

可知匹配不成立，所以要把T向右移位直到得到匹配，返回位置3。

由此可见，BF算法就是一个类似于穷搜的算法，这个算法的时间复杂度为。空间复杂度为

代码实现：

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
#include<stdio.h>
#include<string.h>
#include<windows.h>

int BruteForce(char *S,char *T)
{
	unsigned int i=0,j=0;
	int k=0;
	while(i<strlen(S)&&j<strlen(T))
	{
		if(S[i+k]==T[j])
		{
			k++;
			j++;
		}
		else
		{
			i++;
			j=0;
			k=0;
		}
		if(S[i+strlen(T)-1]==T[strlen(T)-1])
		{
			return i;
			break;
		}
	}
 
}

void main()
{
	char *S,*T;
	S = "abcdabcabdef";
	T = "abcabd";
	int BF;
	BF = BruteForce(S,T);
	printf("%d\n",BF);
	system("pause");
}

KMP算法

上面介绍的Brute-Force算法很简单也相当好理解，但是时间复杂度太高了，最主要的原因是上面的算法耗时，做了一些无用的功。每次把模式串向右移动一步并不够，例如上面的例子我们可以很容易的得到应该把T向右移动3步比较合适，那么怎么让计算机能够做到的，那么我们就需要KMP算法。同时我们也可以看到上面的算法没有利用T中已经匹配了的字符的一些信息。

KMP算法由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的。KMP算法的与BF算法的最大的不同就在于“失配”的处理上，BF算法当遇到失配时，做法是把模式串向右移动一位；而KMP算法则是向右移动更多的位，这个由一个next数组控制，已达到加速的目的。

对上面的例子：

a b c a b c a b d e f

a b c a b d

我们可以得到在位置5处，发生了失配，也就是S[5]!=T[5]。那么对于KMP算法，我们需要将T向右移位，也就是说要另S[5]==T[next[5]];更通用的表述是当S[i]!=T[j]时，令j=next[j]，使S[i]==T[next[j]]，也就是说相当于将T向右移动了j-next[j]>=1位。因此KMP算法的核心就是next数组。next数组只与模式串T的本身性质有关，而与原始串Ｓ无关。

下面我们来看next数组怎样求：

charactor

KMP算法中，如果当前字符匹配成功，即S[i]==T[j]，令i++，j++，继续匹配下一个字符；如果匹配失败，即S[i] != T[j]，需要保持i不变，并且让j = next[j]，这里next[j] <=j -1，即模式串T相对于原始串S向右移动了至少1位(移动的实际位数j - next[j] >=1)。

因此要应用KMP算法，我们首先可以利用模式串T来得到相应的next数组。

  • next[0]=-1: 任何串的首字符的next值为-1；

  • next[j]=-1: 模式串T中下标为j的字符，如果与首字符相同，且j的前面的1—k个字符与开头的1—k个字符不等（或者相等但T[k]==T[j]）（1 ≤ k < j）。

  • next[j]=k: 模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k] （1 ≤ k < j）

  • next[j]=0: 除了上面的情况外其他的情况。

next数组值的意义

设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],

  • next[n]= -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1]和T[0]。

  • next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。

  • next[n]= k >0 但k < n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int *Next(char *T,int *next)
{
	int j = 0, k = -1;
	next[0] = -1;
	while ( T[j] != '\0' )
	{
		 if (k == -1 || T[j] == T[k])
			{
				++j; ++k;
				if (T[j]!=T[k])
					next[j] = k;
				else
					next[j] = next[k];
			 }
		  else
			  k = next[k];
	}
}
显示 Gitment 评论