Next 数组及KMP

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个getnext()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。其中最难理解的部分即next数组的求法以及回溯

前缀数组

**前缀数组中存储的是这个字符串前缀和后缀中相同子串的最长长度 **

next 数组考虑的是除当前字符外的最长相同前缀后缀

以 agctagcagctagctg 为例

** start**

将next数组初始化之后为：

–>将模串依次向后移比较至此

–>回溯

此时对比，小串长为3，j=3;回溯，j=next[j=3]=0;此时i=7;继续匹配依次后移

–>再回溯

此时对比，小串长为3，j=7；回溯，j=next[j]=3,i=14;继续匹配，当pat[i=14]=pat[j=3],i++,j++,即next[15]=4;

–>j=next[j=4]=0;–>j=next[j=0]=-1;–>i++=,j++,next[i=16]=j=0;

** end**

//获取前缀数组
void GetNext(char *pat){
    int i=0,j=-1;
    next[0]=-1;
    while(i<n){                        //n为模板串pat的长度
        if(j==-1||pat[i]==pat[j]){
            i++,j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}




//第二种next数组
//  abcab
//  00012
void calc_next() {
	next[0] = 0;         //下标从1开始  next[1]=0;
	for (int i = 1, j = 0; i < n; i++) { //i=2;i<=n
        while (j > 0 && pat[i] != pat[j])//pat[i]!=pat[j+1]
			j = next[j - 1];             //j=next[j]
		if (pat[i] == pat[j])            //pat[i]==pat[j+1]
			j++;
		next[i] = j;
	}
}

献上一道前缀数组寻找循环节的问题

题号：hdu-1358

题意：一个字符串的前缀是从第一个字符开始的连续若干个字符，例如”abaab”共有5个前缀，分别是a, ab, aba, abaa, abaab。我们希望知道一个N位字符串S的前缀是否具有循环节。换言之，对于每一个从头开始的长度为 i （i>1）的前缀，是否由重复出现的子串A组成，即 AAA…A （A重复出现K次,K>1）。如果存在，请找出最短的循环节对应的K值（也就是这个前缀串的所有可能重复节中，最大的K值）。

输入：输入包括多组测试数据，每组测试数据包括两行。

　　　第一行输入字符串S的长度N。

　　　第二行输入字符串S。

　　　输入数据以只包括一个0的行作为结尾。

输出：对于每组测试数据，第一行输出 “Test case #” 和测试数据的编号。

　　　接下来的每一行，输出具有循环节的前缀的长度i和其对应K，中间用一个空格隔开。

　　　前缀长度需要升序排列。

　　　在每组测试数据的最后输出一个空行。

#include<stdio.h>
#include<string.h>
const int maxn = 1000000 + 5;
char pat[maxn];
int next[maxn];
int len;
void getnext() {
	int i = 0, j = -1;
	next[0] = -1;
	while (i < len) {
		if (j == -1 || pat[i] == pat[j]) {
			i++, j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}
int main()
{
	int t = 0;
	while (scanf("%d", &len) != EOF && len) {
		memset(pat, '\0', sizeof(pat));
		scanf("%s", pat);
		getnext();
		printf("Test case #%d\n", ++t);
		for (int i = 2; i <= len; i++) {
			if (!(i % (i - next[i])) && i / (i - next[i]) != 1)
				printf("%d %d\n", i, i / (i - next[i]));
		}
		printf("\n");
	}
	return 0;
}

KMP 匹配

理解了怎么获得前缀数组，那么我们来浅谈KMP的匹配模式：

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；

如果j != -1, 且当前字符串匹配失败（即s[i] != p[i]）,则令i不变，j = next[j] 。此时意味着匹配失败，模板串pat相对于主串str向右移 j-next[j]。

void KMP()
{
	GetNext(pat);
	int i = 0, j = 0;
	int sum = 0;
	while (i < m)                       //m为主串str长度
	{
		if (j == -1 || str[i] == pat[j])
			i++, j++;
		else
			j = Next[j];
		if (j == n)                     //当前模板串pat与主串str其中一部分匹配成功
            //根据题意添加条件
	}
	return ;
}