本文主要是介绍[算法笔记]kmp算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.kmp算法

kmp算法主要用在字符串匹配上，主要思想是在出现字符串不匹配时，可以知道一部分之前的已经皮匹配的内容，可以利用这些信息不用从头去做匹配。

2.前缀表

前缀表是用来回溯的，它记录了模式串与主串不匹配的时候，模式串应该从哪里开始重新匹配。
前缀表的核心在于，记录下表i之前的字符串中，有多大长度的相同前缀后缀。

如图所示，当指针移动到下标为5的位置，出现了不匹配，此时模式串指向f，如果是朴素比较法，指针应当跳到模式串的开头来匹配，而使用了前缀表来记录之后，**指针只需要跳转到之前字串的最长公共前后缀的前缀的下一个位置。**即下表为2的地方。而不用从0开始重新比较。

由于下标5之前的这部分字符串(aabaa)的最长相等的前缀和后缀字符串是子字符串aa，因为找到了最长相等的前缀和后缀，匹配失败的位置是后面字串的后面，那么我们找到与其相同的前缀后面从新匹配就可以了。

3. 前缀表计算

字符串前缀是指不包含最后一个字符的所有以第一个字符开头的连续字串，后缀是指不包含第一个字符的所有以最后一个字符结尾的连续字串。

前1个字符的字串a，最长相同前后缀长度为0。

前两个字符的字串aa，最长相同前后缀的长度为1。

前三个字符的字串为aab，最长相同前后缀的长度为0。

前四个字符的字串aaba，最长相同前后缀的长度为1。

前五个字符的字符串aabaa，最长相同前后缀长度为2。

长度为6的字符串字串aabaaf，最长相同前后缀的长度为0。

于是取求得的每一个最长相同前后缀的长度就是对应前缀表的元素：

4.前缀表计算（代码实现）

构造一个函数getNext来构建数组，函数参数next数组，和一个字符串。
对模式串s，进行以下三步:

4.1 初始化

定义两个指针i和j，j指向前缀中止位置减一的位置，i指向后缀中止位置。
然后对next数组进行初始化赋值

int j = -1;//前缀表减一的实现版本
next[0] = j;

4.2 处理前后缀不相同的情况

因为j初始化为-1，那么i从1开始，进行s[i]与s[j+1]的比较。
如果s[i]与s[j+1]不相同，就是遇到前后缀末尾不相同的情况，就需要向前回溯。
即next[j]就是记录着j（包括j）之前的字串相同的前后缀的长度。
那么s[i]与s[j+1]不相同，就要找一个j+1前一个元素在next数组里的值（next[j]）

while(j >= 0 && s[i] != s[j + 1]){
	j = next[j]//向前回溯
}

4.3 处理前后缀相同的情况

如果s[i]与s[j+1]相同，那么就同时向后移动i，j，说明找见了相同的后缀，同时还要将j（前缀的长度）赋值给next[i]，因为next[i]要记录相同前后缀的长度。

if(s[i] == s[j + 1]){
	j++;
}
next[i] = j;

4.4 整体构建next数组

void getNext(vector<int>& next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回溯
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

//不减一的版本

void getNext(vector<int>& next, const string& s) {
	int j = 0;
	next[0] = 0;
	for (int i = 1; i < s.size(); i++) {
		while (j > 0 && s[i] != s[j]) {
			j = next[j - 1];//回溯，这里需要看j的前一位
		}
		if (s[i] == s[j]) {
			j++;
		}
		next[i] = j;
	}
}

5.匹配

检查文本串s是否出现过模式串t，定义两个下标i，j，其中j指向模式串的起始位置，i指向文本的起始位置。j的初始值依然为-1（与next前缀表减一的版本保持一致）。遍历文本串，接下来寻找s[i]与t[j+1]是不是相同，如果不相同，j就从next数组中寻找下一个匹配的位置。

while(j >= 0 && s[i] != t[j + 1]){
	j = next[j]
}

如果相同，则ij同时向后移动。

if(s[i] == t[j + 1]){
	j++;//i在for循环里增加
}

当j指到了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个字串了。返回。

if(j == t.size() - 1){
	return (i - t.size() + 1);
}

总体实现：

void getNext(vector<int>& next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回溯
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}
int strStr(string haystack, string needle) {
    if (needle.size() == 0) {
        return 0;
    }
    vector<int> next(needle.size());
    getNext(next, needle);
    int j = -1; // // 因为next数组里记录的起始位置为-1
    for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
        while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
            j = next[j]; // j 寻找之前匹配的位置
        }
        if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
            j++; // i的增加在for循环里
        }
        if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
            return (i - needle.size() + 1);
        }
    }
    return -1;
}

前缀表不减一实现：

void getNext(vector<int>& next, const string& s) {
	int j = 0;
	next[0] = 0;
	for (int i = 1; i < s.size(); i++) {
		while (j > 0 && s[i] != s[j]) {
			j = next[j - 1];//回溯
		}
		if (s[i] == s[j]) {
			j++;
		}
		next[i] = j;
	}
}
int strStr(string haystack, string needle) {
	if (needle.size() == 0) {
		return 0;
	}
	vector<int> next(needle.size());
	getNext(next, needle);
	int j = 0;
	for (int i = 0; i < haystack.size(); i++) {
		while (j > 0 && haystack[i] != needle[j]) {
			j = next[j - 1];
		}
		if (haystack[i] == needle[j]) {
			j++;
		}
		if (j == needle.size()) {  //匹配成功
			return i - needle.size() + 1;
		}
	}
	return -1;
}

这篇关于[算法笔记]kmp算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！