KMP

KMP算法实现

KMP串匹配主要分为两个步骤，即获得match数组(或者说next数组)，然后应用match数组来进行串匹配的简化

1. 获取match数组
   KMP的精髓就在于使用match数组使得i指针不需回退，使得暴力的m*n的时间复杂度变为m+n的时间复杂度，其中的m指的就是求match数组的复杂度。

match数组的含义为，当当前字符与主串匹配失败时，我们并不直接整个回退两个指针，而是寻求一个前缀字符串(即从头开始的子串)可以和以该字符串前一个字符为后缀的字串相匹配，使得模式串不需回退到头，而是从该前缀字符的最后一个字符开始匹配

下面是求match数组的代码，主要的思想就是迭代求解。
注意这里的match数组要求下标从0开始

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 20;
int match[N];
string pattern;
string str;
void get_match()
{
	match[0] = -1;//第0个字符显然没有前缀字串，赋值为-1
	for (int i = 0; i < pattern.size(); i++)//遍历模式串的每一个字符，寻找可以与其匹配的模式串
	{
		int now_match = match[i - 1];
		while (now_match > 0 && pattern[now_match + 1] == pattern[i])//当该前缀与后缀不匹配时，递归(迭代？）进行求解，去找一个更小的前缀
			now_match = match[now_match];
		if (pattern[now_match + 1] == pattern[i])//循环退出，若相等则为找到了
			match[i] = now_match + 1;
		else // 不等则没有这样的前缀，赋值为-1
			match[i] = -1;
	}
}

接下来是KMP算法的实现、

void KMP()
{
	int i = 0, j = 0;
	while (i < str.size())//主串还未到头就继续
	{
		if (str[i] == pattern[j])//若当前字符可以匹配，双指针都向后移动一位
		{
			i++;
			j++;
		}
		else if (j > 0)//若匹配不上，尝试移动j寻找match[j - 1] + 1（为防止越界j > 0）
		{
			j = match[j - 1] + 1;
		}
		else//j <= 0 ,说明第一个字符就匹配不上，主串指针向后移动一位
		{
			i++;
		}
		if (j == pattern.size()) // 当匹配长度等于模式串时，匹配成功，输出其起始位置，同时为了匹配下一个可能的模式串，j指针同理移动
		{
			cout << i - j << endl;
			j = match[j - 1] + 1;
		}
			
	}
}