【代码记录】进一步理解kmp中的next数组

【代码记录】进一步理解kmp中的next数组

kmp是一种改进的字符串匹配算法在字符串的匹配问题中，最坏情况下可能需要将目标串全部走完才能完，对于最朴素的做法而言，时

间复杂度可能达到O（子串*目标串），当目标串非常长时，时间复杂度也会非常大。这时候就需要kmp算法来优化。

在对kmp算法有所了解后，我们知道kmp的重点就在于求出next数组，更深入的了解next数组可以做题：

https://www.luogu.com.cn/problem/P4391

https://www.luogu.com.cn/problem/UVA10298

https://www.luogu.com.cn/problem/P2445

对于next[]的理解

next[k] 表示下标为k的字符前面的子串的最长相等前后缀的长度

 同时，next数组的值也表示当字符串不匹配是字符应当回溯的位置。当当前字符不匹配时，就需要回溯，重新去找最长相等前后缀的长度。

 对于next数组的理解和应用是kmp算法的重中之重，在运用kmp时不一定会考字符串的匹配，也会考对next数组的运用。

求next数组代码1

void GetNextval(char* p, int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1, j = 0;
	while (j < pLen - 1)
	{//p[k]表示前缀，p[j]表示后缀  
		if (k == -1 || p[j] == p[k])
		{
			++j,++k;
			if (p[j] != p[k])
				next[j] = k;   
			else
				next[j] = next[k];
		}
		else
			k = next[k];
        //next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
        // 也表示该处字符不匹配时应该回溯到的字符的下标
}

acm中更简便的写法

for(int i=2;i<=len;i++)
   {
       while(j&&ne[j+1]!=a[i])  j=ne[j];
       if(a[j+1]==a[i]) j++;
         ne[i]=j;
}