KMP算法的一些注意事项

前言：这是一个比较困难的算法，每次学每次忘，究其原因是没有彻底理解，今天我通过各种过去的学习资料和记录，详细总结一下我个人在学习中认为要注意的事项和原因。同样，由于时间和水平有限，这并非是一个教学文章，仅仅用于个人记录。

前缀表prefix table

kmp就离不开前缀表，我们是通过最要匹配的的子串t进行分析，得出next数组后，才能利用kmp算法进行高效率匹配。

那其实很多时候我都只是记住算法的格式：比如abcabd,a的前缀对称数为0，ab为0，abc为0，abca为1，abcab为2,abcabd为0，然后最后一个本身的对称数不用，在最前面加一个-1。

其实这就是next数组。

但是为什么？其实仔细想后并不难，比如说拿字符串t去匹配s,我们针对t进行了分析，哦，那假设t的第5个字符t[4]的next[4]为1，那说明什么？就是这个第五个字符的前缀t[0]t[1]t[2]t[3]对称数为1，第一个字符和第四个字符是一样的，如果假设就匹配到了第5个字符时，t[4]!=s[i]，那t字符串的索引j要跳到t[next[4]]重新匹配，为什么啊，因为既然匹配到了第五个字符时才不对应，那说明第四个字符是对应的，那第四个字符又等于第一个字符，所以我们不需要去再匹配第一个字符了，而且遵循主串s的索引i不回溯原则，我们直接拿t[next[4]]也就是t[1]来和s[i]匹配。至于-1这个位置，那就i,j同时加一即可。

 具体而言：

s:aabaaghiafa

t:aabaaf

那么我们可以看到f不匹配，而next[5]=2,所以拿t[2]，也就是b去和s的g进行比对。

实际上前缀串表示的是除了当前字符外，前面的字符串。ababc的c的前缀字符串就是abab，所以next[4]=2。

注意我这里说的是对称，有的书也说最长相等前后缀（前缀不包括尾字母，后缀不包括首字母,ababc中求next[4],就是找到最长相等前后缀ab），关键明白这个意思即可。

代码怎么写

先看个例子：

先求next数组

得先求前缀表，再转化为next,转化就是所有往前挪一位，最前面再加负一。（这些都是为了后面代码好写一点）

如果这样难理解，那么就这样想：next[0]永远等于-1。然后我们看数组索引为n的字符时，我们只在索引0到n-1的字符串里面找所谓的对称树，或者叫最长相等前后缀长度，作为next[n]的值

关键是，我们可以这样分析，但是代码怎么写，怎么去分析出prefix[]数组来呢？知道prefix后其实也就知道了next

所以要写代码就要发现规律：

 观察这两个，prefix的值是怎么从1变成2的呢？

想让最长相等前后缀变长，那只能在最后一个地方加上一个B，所以匹配到索引为n的字符时，想让长度从1变成2，就需要t[n]=t[1]。再一般一点匹配到索引为n的字符时，想让长度从l变成l+1,就需要  if(t[n]==t[l+1-1]) ++len;prefix[n]=len;++n;

else{lem=prefix[len-1];}

ABABCABAA,设next数组的下标为k,t字符串数组的下标为j,len=9,所以当j=7的时候，k=3,t[3]=t[7],然后j++,k++,好，到最后一位了，t[8]!=t[4],这个时候就按上面的说法，回溯，k=t[k-1]

 

今天突然对回溯有点感觉了：

看这个评论：

 我们很朴素地去想，设next数组的下标为k,t字符串数组的下标为j,先假如此时t[k]=t[j],于是k++,j++,,额不妨设加了之后，k=3,j=9,那么此时t[k],也就是此时拿出的前缀字符串的最后一位，和t[9]不匹配，那不就说明我们拿出来的前缀太长了，我们需要拿更短一点的前缀，但是我们又不能直接说,    k--,这样很容易找到出错的例子，所以根据dp的思想，当前状态取决于上一个状态，于是乎，k=next[k-1],也就是说，至少我们知道上一次匹配的时候，k=2结尾的前缀串是可以找到匹配的后缀串的，那就一个个往前匹配，前缀也在不断缩短。

如果不相等呢？记住，kmp的核心就是当s[i]和t[j]发生不匹配现象时，i指针不需要回溯，只需j指针回溯。而next数组其实就在实现回溯，所以这里其实不能只关注next了，而是从s,t匹配的角度去思考怎么回溯：j=next[j-1]

现在假设t[j-1]==s[i-1],t[j]!=s[i],那说明至少前面0到j-1的字符还是可以匹配的，所以想到上面说过的，aabaaf,我们应该找到b，next[5]=2,那next[5]是怎么来的呢

绝对超级详细的kmp算法，next数组求法，以及回溯的理解_Daaaale的博客-CSDN博客_kmp next求法

图解KMP以及next数组的求法 - roccoshi - 博客园

算了，真的很难记录，要自己理解，下面给两段代码：

void get_prefix(char pattern[],int prefix[],int n)
{
	prefix[0]=0;//初始化，第一个就是0,
	int len = 0;
	int i = 1;
	while(i < n)
	{
		if(pattern[i] == pattern[len])
		{
			len++;
			prefix[i] = len;
			i++;
		}
		else{
			if(len>0)
			{
				len = prefix[len-1];
			}
			else{					//初始len=0 
				prefix[i] = len;//len这时肯定等于0 
				i++;
			}
		}
	}
}
 
void move_prefix(int prefix[],int n) 
{
	int i;
	for(i = n-1;i > 0;i--)
	{
		prefix[i]=prefix[i-1];
	}
	prefix[0]=-1;//为了方便后面的代码 
}
 
void kmp_search(char text[],char pattern[])
{
	
	int n = strlen(pattern);
	int m = strlen(text);	
	
	int *p=(int*)malloc(sizeof(int)*n);//这只是一个尝试 
	 
	int prefix[n+1];//创建数组并且是int，且乘以大小n 
	get_prefix(pattern,prefix,n);
	move_prefix(prefix,n);
	
	int i=0;
	int j=0;
	
	while(i
	{		
		if(j==n-1&&text[i]==pattern[j])
		{
		
			printf("Founf pattern at %d\n", i-j);
			j=prefix[j];
		}
		
		if(j==-1||text[i]==pattern[j])
		{
			i++;j++;
		}
		else{
			j=prefix[j];
		}
	}
	
	cout<
	for(int p=0;p
	{
		cout<' ';
	}
} 

然后直接求开始下标为-1的Next数组：

#include"bits/stdc++.h"
 
using namespace std;
 
const int MAXN=105;
 
void get_next(string s,int *next)
{
	next[0]=-1;
	int len=s.length();
	int k=-1;	
	int i=1;
	while(i
	{
		if(k==-1||s[k]==s[i - 1])
		{
			k++;
			next[i]=k;
			i++;
		}
		else
		{
			k=next[k];
		}
	}	
}
 
int searchkmp(string s1,string s2,int pos,int next[])//pos从0开始算
{
 
	int i,j;
	i=pos;
	j=0;
	while(ilength()&&jlength())
	{
		if (j == n - 1 && s1[i] == s2[j]) {
 
			printf("Founf pattern at %d\n", i - j);
			j = next[j];
		}
 
		if(j==-1||s1[i]==s2[j])
		{
			j++;
			i++;
		}
		else
		{
			j=next[j];
		}
	}
 
	if(j==s2.length())
	{
	
		return  i-s2.length();
	}
	else return -100;	
}