【数据结构----KMP算法】校招笔试题总结

根据KMP算法求得的next数组

基础知识:
模式匹配： 从某个字符串中找出与一个给定子串相同的子串的位置。简单说就是从一个字符串中找出是否含有另一个字符串，若存在则返回位置.
常用的模式匹配算法有：BF（朴素模式匹配算法或暴力匹配算法）、BM算法、RK算法、KMP算法。
主串： 待查找的字符串。
模式串（子串）： 模式匹配就是要从主串中找到子串。
KMP算法： 是一种改进BF算法的模式匹配算法。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
前缀： 字符串的开头，例如字符串abcd的前缀为a, ab, abc, abcd。在KMP算法中使用的前缀为真前缀，既不包括原字符串abcd的前缀。（真前缀：a, ab, abc）
后缀： 字符串的结尾，在KMP算法中同样使用的是真后缀。
最长公共前后缀： 最长的相等的前缀与后缀，例如字符串ABCxyzABC的最长公共前后缀为ABC

BF算法

BF算法就是暴力匹配算法，是最好理解的算法。就是对主串一位一位的做判断，匹配失败则将模式串向后移动一位，如下图所示。
在极端条件下BF算法要匹配(N-M+1)M次（其中N为主串长度，M为模式串长度），所以BF算法的时间复杂度为O(MN)。

求next数组

求字符串abaabcac的next数组
next[1] = 0
next[2] = 1
当i > 2 时，如：求next[5]
求next[0]~next[i - 1]所构成的串的首子串和尾子串（首子串不包括最后一个，尾子串不包括第一个）
next[0]~next[4]为：abaa
首子串：a，ab，aba
尾子串：baa，aa，a
计算首尾子串中相同的子串的长度
相同的子串为a，长度为1
next[i] = length + 1
求得长度为1,1+1 = 2，所以next[5] = 2

KMP算法

MP算法优化了BM算法，通过一次尽可能多的向右移动来减少匹配次数。KMP算法的时间复杂度只有O(M+N)。

KMP算法利用了最长公共前后缀的值来进行移动:

KMP算法实现

版本一

//next[0] = -1 版本
void getNext(char * p, int * next){
	next[0] = -1;
	int i = 0, j = -1;
	while (i < strlen(p)){
		if (j == -1 || p[i] == p[j]){
			++i;
			++j;
			next[i] = j;
		} else	j = next[j];
	}
}
int KMP(char * t, char * p) 
{
	int i = 0; 
	int j = 0;
	while (i < strlen(t) && j < strlen(p)){
		if (j == -1 || t[i] == p[j]){
			i++;
           	j++;
		} else 	j = next[j];  
    }
    if (j == strlen(p))
       return i - j;
    else 
       return -1;
}


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

版本二

next[0] = 0 版本
int TLens = 0,SLens = 0;
void get_nextval(char T[], int next[]){
    int i=1, j =1;
    next[0] = 0;
    TLens = T[0];
    while(i < TLens){
        if(j == 0 || T[i]==T[j]){
            ++i;
			++j;
            next[i] = j;
        } 
		else j = next[j];
    }
}
int Index_KMP(char S[], char T[], int pos, int next[]){
	SLens = S[0];
    int i=1, j=1;
    while(i < SLens && j < TLens){
        if(j == 0 || S[i] == T[j] ){
            ++i,++j;
        } else j = next[j];
    }
    if( j == TLens)
        return i-j+1;
    else return 0;
}


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