【算法】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);
}