KMP算法实现
KMP串匹配主要分为两个步骤，即获得match数组(或者说next数组)，然后应用match数组来进行串匹配的简化
- 获取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;
}
}
}