KMP算法_kmp算法思想

KMP算法

一、KMP基本思想：
KMP主要应用在字符串匹配的场景中，其主要思想是当出现字符串不匹配的情况时，可以知道一部分之前已经匹配的的文本内容，利用这些信息避免从头再去做匹配，而其中前缀表担负重任。

二、前缀表：

1、前后缀：
字符串的前缀：不包含最后一个字符的所有以第一个字符开头的连续子字符串
字符串的后缀：不包含第一个字符的所有以最后一个字符结尾的连续子字符串

2、next数组：

next数组是一个前缀表，或者说是前缀表达的某种变形，记录模式串下标i（包括i）之前的字符串中有多长的相同的前后缀。
前缀表是用来回退的，它记录了模式串与文本串不匹配的时候，模式串应该从哪里开始重新匹配的信息。当模式串与文本串匹配失败后，找到之前已经匹配的位置再重新匹配，前缀表会告诉你下一步匹配的时候模式串的当前下标应该跳到哪个位置。
next数组可以是前缀表，但也有一些实现方法是把前缀表统一减一或者整体右移一位，初始位置为-1，这样操作之后的前缀表将作为next数组。

三、计算前缀表：

以该串为例子：

得到前缀表，然后进行匹配：
当文本串和模式串遇到第一个不匹配的字符时，则寻找前缀表中再当前位置的前一个位置的值m然后将模式串当前位置（箭头指向）回退到下标该值为m的位置，继续匹配
前缀表统一减一：则模式串当前位置：回退到前缀表当前位置前一个位置的值+1的下标处
前缀表整体向右移：则模式串当前位置：回退到前缀表当前位置前位置的值的下标处


继续往后匹配，不匹配就根据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开始，i作为后缀的起始位置
	{
   
		
1
2
3
4
5
6
7
8
9
10