2021年SWPUACM暑假集训day4KMP算法

KMP算法 前言

配套视频：

www.bilibili.com/video/BV18f4y1L7Uh

KMP算法（也叫看猫片算法(bushi）是Knuth、Pratt 和 Morris 在 1977 年共同发布一个在线性时间(O(n+m))字符串查找或匹配算法，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。

一、前缀和后缀 1.1前缀

是指的从串首到某个位置i结束的一个子串

1.2真前缀

是指的是除开该串本身的前缀

1.3后缀

指从某个位置i开始到整个串末尾结束的一个子串

1.4真后缀

是指的是除开该串本身的后缀

二、前缀函数(next)

给定一个长度为 n的字符串 S，其 前缀函数 被定义为一个长度为n的数组 next。 其中next[i]的定义是：

1.如果子串S[0,……,i]有一对相等的真前缀与真后缀：S[0,……,k-1]和S[i-(k-1)……i]，那么next[i]就是这个相等的真前缀的长度(或者真后缀，因为这两个值是相等的)，即next[i] = k;

2.如果不止有一对相等的，那么next[i]就是最长的那个

3.如果没有相等的那么next[i]就是0

假定字符串S为 a b c a b c a abcabca abcabca

那么next数组的值为

next[i]值next[0]-1next[1]0next[2]0next[3]0next[4]1next[5]2next[6]3next[7]4

这里就能看出字符串abcabca的前缀函数数组为[-1,0,0,0,1,2,3,4],注意一下这里的next[0]是用于辅助计算前缀值的，next数组求出的前缀值是求的长度为i的字符串的最大真前缀长度，也就是最大i-1

不难发现next数组的值的增加是一步一步的，也就是相邻的两个next值的差值最大为1，也就是说匹配成功后我们可以接着使用这个数据，失败则通过我们的next数组进行回溯，因为前后缀相同，我们不难得出下面的计算next数组的代码

const int N = 1e6+10;
int nextt[N];
char S[N];
int len1;
void get_next() {
	int i = 0,j = -1;
	nextt[0] = -1;//这个是辅助计算next值得
	while(i  j = 0，其实我们会发现对于这种情况我们其实可以直接让最后一个a直接指向0，这样在我们匹配的过程中就能减少很多不必要的操作
 
代码实现:
 
const int N = 1e6+10;
int nextt[N];
char S[N];
int n;
void get_next() {
	int i = 0,j = -1;
	nextt[0] = -1;//这个是辅助计算next值得
	while(i