kmp算法

前言

何为kmp算法，就是在住字符串寻找我们需要的字符，并输出其位置，最为广泛的运用就是我们在百度输入一个名词，然后百度就会给我们许多的搜索发现这些发现就是通过kmp算法查找出来的。kmp我认为挺难理解的。

过程

kmp算法就是相当于一个动态规划的过程，进可攻，退可守，退而求其次。
接下来讲一下真前缀和真后缀：前缀就是除了最后一个字母之前的字符串，真后缀就是除了最前面一个字母后面的字符串。

最精华的思路就是使用一个next数组，每个next数组里面存放的是这个位置最大的相同的前后缀的长度，每次没有寻找到结果就需要将j的值重新赋给j这样就会是的j回到前后缀最大相同的地方，所以这个kmp算法的精髓就在于将next每一下标的算出来，那么如何将这个值算出来呢？
思路：首先我们需要一个for将主串的所以字符全部遍历一遍，这样它的时间复杂度就是n，同时这样也可以保证将全部的字符遍历一遍，如果遇到和模式串不相同的字符就进行回溯，如果遇到相同的就进行j++看接下来的字符是否相同，这个就是kmp算法的精髓所在。
接下来我们来看两个列题
 

 【模板】KMP

 这个就是kmp的模板这个模板有利于我们理解kmp的全过程

按照我之前给思路将个代码写出来：

#include<iostream>
#include<string.h>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e6 + 20;
char s1[N];
char s2[N];
int kmp[N];
int main()
{
	scanf("%s", s1 + 1);
	scanf("%s", s2 + 1);
	int len1 = strlen(s1 + 1);//计算下标为1开始到\0之前有多少个字符
	int len2 = strlen(s2 + 1);
	int j = 0;
	kmp[1] = 0;//无论这个模式串是怎样的，开始下标为1所存的树一定是0
	for (int i = 2; i <= len2; i++)//开始构建next数组
	{
		while (j > 0 && s2[i] != s2[j + 1])//如果不等于就回溯，这里解释一下为什么是j+1,因为是回溯所以j前面的都是相同的，要从j这个位置开始回溯
			j = kmp[j];
		if (s2[i] == s2[j + 1])
			j++;
		kmp[i] = j;//next数组记录的是前后后缀最大相同的长度
	}
	j = 0;
	for (int i = 1; i <= len1; i++)
	{
		while (j > 0 && s1[i] != s2[j + 1])
			j = kmp[j];
		if (s1[i] == s2[j + 1])
			j++;
		if (j == len2)
		{
			cout << i - len2 + 1 << endl;
			j = kmp[j];//如果找到了，就要回溯，又可能答案会重叠，所以需要靠着养的方式堆j进行初始化
		}

	}
	for (int i = 1; i < len2; i++)
	{
		cout << kmp[i] << " ";
	}
	cout << kmp[len2];
	return 0;
}

Radio Transmission 无线传输

 我们仔细思考一下是不是相同的字符串绝对会出现在中间（这个中间同时也包括最前面也包括最后面）所以我们只要考虑最后一位的最大前后缀长度，在拿全部的数组长度减去最大前后缀和就可以将最小的重复字符串算出来了
代码如下
 

#include<iostream>
#include<string.h>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e6 + 20;
char s1[N];
char s2[N];
int kmp[N];
int main()
{
	scanf("%s", s1 + 1);
	scanf("%s", s2 + 1);
	int len1 = strlen(s1 + 1);//计算下标为1开始到\0之前有多少个字符
	int len2 = strlen(s2 + 1);
	int j = 0;
	kmp[1] = 0;//无论这个模式串是怎样的，开始下标为1所存的树一定是0
	for (int i = 2; i <= len2; i++)//开始构建next数组
	{
		while (j > 0 && s2[i] != s2[j + 1])//如果不等于就回溯，这里解释一下为什么是j+1,因为是回溯所以j前面的都是相同的，要从j这个位置开始回溯
			j = kmp[j];
		if (s2[i] == s2[j + 1])
			j++;
		kmp[i] = j;//next数组记录的是前后后缀最大相同的长度
	}
	j = 0;
	for (int i = 1; i <= len1; i++)
	{
		while (j > 0 && s1[i] != s2[j + 1])
			j = kmp[j];
		if (s1[i] == s2[j + 1])
			j++;
		if (j == len2)
		{
			cout << i - len2 + 1 << endl;
			j = kmp[j];//如果找到了，就要回溯，又可能答案会重叠，所以需要靠着养的方式堆j进行初始化
		}

	}
	for (int i = 1; i < len2; i++)
	{
		cout << kmp[i] << " ";
	}
	cout << kmp[len2];
	return 0;
}