【算法】C++KMP算法的简洁实现

目录

简介

next数组

匹配

完整代码

---

简介

对于朴素的字符串匹配算法，如果想在主串中寻找到第一次出现子串的位置，需要依次枚举主串中的每一个位置作为起始位置进行匹配尝试，如果主串中存在许多与子串相似结构的部分，那么朴素算法会进行大量的无用枚举，时间复杂度非常之高。

KMP算法区别于朴素算法的地方就是其在尝试匹配时，匹配失败后不会回溯主串的指针，而是通过一个预处理的next数组去回溯子串的指针，主串的指针会继续向后遍历。

因此KMP算法只会遍历一次主串，这在主串长，子串短的情况下具有非常大的性能优势。

next数组

next数组是用于指挥子串指针会回溯到子串的哪个位置，这个数组需要在执行真正的匹配算法前预处理出来，以下是其预处理的代码

//构造next数组
//m代表子串长度
vector<int> next(m, 0);
for(int i = 0; i < m; i++)
{//从当前位置向前寻找子串中最近的和当前字符一样的字符//并记录最近的字符的位置到next中当前字符的对应位置上for(int j = i - 1; j >= 0; j--){if(subStr[j] == subStr[i]){next[i] = j;break;}	}
}

匹配

接下来通过next数组进行只回溯子串指针的匹配算法

//遍历主串寻找子串位置，不回溯主串，通过next数组回溯模式串
int j = 0;
for(int i = 0; i < n; i++)
{//如果匹配，两个指针共同前进while(str[i] == subStr[j] && j < m){j++;i++;}//结束后区分下是while中哪个条件导致的//匹配成功if(j >= m)return i - m;//匹配出现失败，通过next指针进行回溯j = next[j];
}return -1;	//没找到

完整代码

以下是完整代码

#include <iostream>
#include <vector>
using namespace std;void printer(const vector<int>& arr)
{for(int i : arr)cout << i << " ";cout << endl;
}int FindKMP(const string& str, const string& subStr)
{int n = str.size(), m = subStr.size();//构造next数组vector<int> next(m, 0);for(int i = 0; i < m; i++){for(int j = i - 1; j >= 0; j--){if(subStr[j] == subStr[i]){next[i] = j;break;}	}}//遍历主串寻找子串位置，不回溯主串，通过next数组回溯模式串int j = 0;for(int i = 0; i < n; i++){//如果匹配，两个指针共同前进while(str[i] == subStr[j] && j < m){j++;i++;}//结束后区分下是while中哪个条件导致的//匹配成功if(j >= m)return i - m;//匹配出现失败，通过next指针进行回溯j = next[j];}return -1;	//没找到
}int main()
{string str = "746381982378";string subStr = "82378";cout << FindKMP(str, subStr);
}