KMP算法及其改进算法

	思路：从主串的第一个位置起和模式串的第一个字符开始比较，如果相等，则继续逐一比较后续字符；否则从主串的第二个字符开始，再重新用上一步的方法与模式串中的字符做比较，以此类推，直到比较完模式串中的所有字符。若匹配成功，则返回模式串在主串中的位置；若匹配不成功，则返回一个可区别于主串所有位置的标记，如“0”。

int index(Str str,Str substr)
{
    int i = 1,j = 1,k = 1;//串从数组下标1位置开始存储，初值为1
    while(i <= str.length && j <= substr.length)
    {
        if(str.ch[i] == substr[j])
        {
            i++；
            j++;
        }
        else
        {
            j = 1;
            i = ++k;//匹配失败，i从主串的下一个位置开始匹配，k储存了主串上一次的起始位置
        }
    }
    if(j > substr.length)
        return k;
    else ruturn 0;
}

	设主串为s1s2...sn,模式串为p1p2...pm，在上面的匹配过程中，经常出现一个关键状态（表2），其中i和j分别为主串和模式串中当前参与比较的两个字符的下标。

	模式串的前部某子串P1P2...Pj-1与主串中的一个子串Si-j+1Si-j+2...Si-1匹配，而Pj与Si不匹配。每当出现这种状态时，简单模式匹配算法的做法是:一律将i赋值为i-j+2，j赋值为1，重新开始比较。这个过程反映到表2中可以形象地表示为模式串先向后移动一个位置，然后从第一个字符P1开始逐个和当前主串中对应的字符做比较；当再次发现不匹配时，重复上述过程。这样做的目的是试图消除Si处的不匹配，进而开始Si+1及其以后字符的比较，使得整个过程得以推进下去。

	如果在模式串后移的过程中又出现了其前部某子串P1P2…与主串中某子串…Si-2Si-1相匹配的状态，则认为这是一个进步的状态。因为通过模式串后移排除了一些不可能匹配的状态，来到了一个新的局部匹配状态，并且此时Si有了和模式串中对应字符匹配的可能性。为了方便表述，记表中描述的状态为Sk，此处的新状态为Sk+1，此时可以将简单模式匹配过程看成一个由Sk向Sk+1推进的过程。当由Sk来到Sk+1时有两种情况可能发生:其一，S处的不匹配被解决，从si+1继续往下比较，若来到新的不匹配字符位置，则模式串后移寻找状态Sk+2；其二，Si处的不匹配仍然存在，则模式串继续后移寻找状态Sk+2如此进行下去，直到得到最终结果。

	**说明:为了使上边其一与其二的表述看起来清晰工整且抓住重点，此处省略了对匹配成功与失败这两种容易理解的情况的描述。**

	**说明:模式串后移使P1移动到Si+1，即模式串整个移过Si的情况也认为是Si处的不匹配被解决。试想，如果在匹配过程中可以省略掉模式串逐渐后移的过程，而从Sk直接跳到Sk+1，则可以大大提高匹配效率。带着这个想法，我们把Sk+1状态添加到表2中得到表3。**

	观察发现，P1P2...Pj-1和Si-j+1Si-j+2...Si-1是完全相同的，且我们研究的是从Sk跳到Sk+1，因此，删除表3关于主串的一行，得到表4。

	由表4可知，P1P2...Pt-1和Pj-t+1Pj-t+2...Pj-1匹配。记P1P2..Pj-1为F，记P1P2...Pt-1为FL，记Pj-t+1Pj-t+2...Pj-1为FR。所以，只需将F后移到使得FL和FR重合的位置（上表有色部位），即可实现Sk直接跳到Sk+1。

总结一般情况：每当发生不匹配的时候，找出模式串当中的不匹配的那个字符Pj，取其之前的子串F=P1P2...Pj-1，将模式串后移，使**F最先发生前部（FL）与后部（FR）相重合**的位置（见表中有色区域所示），即为模式串应后移的目标位置。

	为了使问题表述得更形象，采用了模式串后移这种分析方式。事实上，在计算机中模式串是不会移动的，因此需要把模式串后移转化为j的变化，模式串后移到某个位置可等效于j重新指向某位置。容易看出，j处发生不匹配时，**j重新指向的位置恰好是F串中前后相重合子串的长度+1（串F或F长度+1）**。通常我们定义一个next］数组，其中j取1~m，m为模式串长度，表示模式串中第j个字符发生不匹配时，应从next］处的字符开始重新与主串比较。

	1）模式串中的第一个字符与主串i位置不匹配，应从下一个位置和模式串第一个字符继续比较。反映在从si+1与p1开始比较。

	2）当串F中不存在前后重合的部分时（不可将F自身视为和自身重合），则从主串中发生不匹配的字符与模式串第一个字符开始比较，反映在表4-2中即从s1与p1开始比较。

	1）当j等于1时发生不匹配，属于特殊情况1，此时将next［1］赋值成0来表示这个特殊情况。

	2）当j等于2时发生不匹配，此时F为“”，属于特殊情况2），即next［2］赋值为1。

	3）当j等于3时发生不匹配，此时F为“AB”，属于特殊情况2），即next［3］赋值为1。

	4）当j等于4时发生不匹配，此时F为“ABA”，前部子串A与后部子串A重合，长度为1，因此next［4］赋值为2（F或FR长度+1）。

	5）当j等于5时发生不匹配，此时F为“ABAB”，前部子串AB与后部子串AB重合，长度为2，因此next［5］赋值为3。

	6）当j等于6时发生不匹配，此时F为“ABAB”，前部子串ABA与后部子串ABA最先发生重合，长度为3，因此next［6］赋值为4。

	7）当j等于7时发生不匹配，此时F为“ABABAB”，前部子串ABAB与后部子串ABAB最先发生

	**注意:6）和7）中出现了“最先"字眼，以7）为例，F向后移动，会发生两次前部与后部的重合，第一次是ABAB，第二次是AB，显然最先发生重合的是ABAB.之所以选择最先的ABAB，而不是第二次的AB，是因为模式串是不停后移的，选择AB则丢掉了一次解决不匹配的可能性，而选择ABAB，即使当前解决不了，则下一个状态就是AB，不会丢掉任何解决问题的可能。这里也解释了一些参考书中提到的取最长相等前后的原因，7）中的ABAB或AB在一些参考书中称为F的相等前后缀（即FL和FR为F的相等前后缀），ABAB是最长相等前后缀，并且很显然的是，越先发生重合的相等前后缀长度越长。**

	上述方法为手工求next数组的方法。介绍一下适用于转换成代码的高效的求next数组的方法。

	假设next[j]的值已知，则next[j+1]的求值可以分两种情况分析。

	1）若Pj等于Pt，显然next[j+1]=t+1，因为t为当前F最长相等前后缀长度（t为FL和FR长度）。

	2）若Pj不等于Pt，将Pj-t+1Pj-t+2...Pj当作主串，P1P2...Pt当作子串，则***又回到了由状态Sk找Sk+1的过程***，所以只需将t赋值为next[t]，继续进行Pj与Pt的比较，如果满足1）则求得next[j+1]，不满足则重复t赋值为next[t]，并比较Pj与Pt的过程。如果在这个过程中t出现等于0的情况，则应将next[J+1]赋值为1，此处类似于上边讲到的特殊情况2）。

	**说明:Sk直接跳到Sk+1，也就是通常所说的简单模式匹配算法中i不需要回溯。**

void getnext(Str substr,int next[])
{
	int i = 1,j = 0;//串从下标为1的位置开始存储，i初值为1
	next[1] = 0;
	while(i < substr.length)
    {
		if(j == 0 || substr.ch[i] == sbustr[j])
        {
			++i;
			++j;
			next[i] = j;
		}
		else
			j = next[j]//理解这一点，回溯
	}
}

	得到next数组后，将简单模式匹配算法稍作修改就可以由状态Sk直接跳到Sk+1的改进算法，这就是知名的KMP算法，代码如下：

int KMP(Str str,Str substr,int next[])
{
	int i = 1,j = 1;//串从数组下标1处开始
	while(i <= str.length && j <= substr.length)
    {
		if(j == 0 || str.ch[i] == substr.ch[j])
        {
			++i;
			++j;
		}
		else
			j = next[j];
	}
	if(j > substr.length)
		return i - substr.length;
	else
		return 0;
}

	先看一种特殊情况，见表7。当j等于，发生不匹配时，因next[5]=4，则需将j回溯到4进行比较；又因next[4]=3，则应将j回溯到3进行比较…由此可见，j需要依次在5、4、3、2、1的位置上进行比较，而模式串在1到5的位置上的字符完全相等，因此较为聪明的做法应该是在j等于5处发生不匹配时，直接跳过位置1到4的多余比较，这就是KMP算法改进的切入点。

	将上述过程推广到一般情况为：

	若Pj等于Pk1（k1=next[j]），则继续比较Pj与Pk2（k2=next[next[j]]），若仍相等则继续比较下去，直到Pj与Pkn不等（kn=next[next[next[j]…]]，嵌套n个next）或kn等于0时，则next[j]重置为kn。一般保持next数组不变，而用名为 nextval的数组来保存更新后的next数组，即当Pj与Pkn不等时， nextval[j]赋值为kn。

	下面通过一个例题来看一下 nextval的推导过程。

	【例】求模 ABABAAB式串的next数组和 nextval数组。

	首先求出next数组，见表8。

	1）当j为1时，nextval[1]赋值为0，特殊情况标记。

	2）当j为2时，P2为B，Pk1（k1=next[2]，值为1）为A，两者不等，因此 nextval[2]赋值为1。

	3）当j为3时，P3为A，Pk1（k1=next[3]，值为1）为A，两者相等，因此应先判断k2是否为0，而k2等于next[next[3]]，值为0，所以 nextval[3]赋值为k2，值为0。

	**注意:步骤3）中P3与Pk1（k1=next[3]）比较相等后，按照之前的分析应先判断k2是否为0，再让P3继续与Pk2比较，注意到此时 nextval[next[3]]即 nextval[1]的值已经存在，故只需直接将 nextval[3]直接赋值为 nextval[1]即可，即 nextval[3]=nextval[3]=0。**

	**推广到一般情况为:当Pj等于Pk1（k1=next[j]）时，只需让 nextval[j]赋值为 nextval[next[j]]即可。原因有两点：**

	**① nextval数组是从下标1开始逐渐往后求得的，所以在求 nextval[j]时， nextval[next[j]]必已求得。**

	**② nextval[next[j]]为Pj与Pk2到Pkn比较结果的记录，因此无须再重复比较。**

	4）当j为4时，P4为B，Pk（k=next[4]）为B，两者相等，因此 nextval[4]赋值为 nextval[next[4]]值为1。

	5）当j为5时，P5为A，Pk（k=next[5]）为A，两者相等，因此nextval[5]赋值为nextval[next[5]]，值为0。

	6）当j为6时，P6为A，Pk（k=next[6]）为B，两者不等，因此nextval[6]赋值为next[6],值为4。

	7）当j为7时，P7为B，Pk（k=next[7]）为B，两者相等，因此nextval[7]赋值为nextval[next[7]],值为1。

	由此求得nextval数组见表9

	总结求nextval的一般步骤：

	1）当j等于1时，nextval[j]赋值为0，作特殊标记。

	2）当Pj不等于Pk时（k=next[j]），nextval[j]赋值为k。

	3）当Pj等于Pk时（k=next[j]），nextval[j]赋值为nextval[k]。

	求next数组的函数getnext()的核心代码段：

if(j == 0 || substr.ch[i] == substr.ch[j])
{
	++i;
	++j;
	next[i] = j;//1
}
else
	j = next[j];//2

	在注释1处next[i]已求出，且next[0...i-1]皆已求出，则结合上边的总结，要求nextval，可以在1处添加以下代码

next[i] = j;//1：i处不匹配，应跳回j处
if(substr.ch[i] != substr.ch[next[i]])
	nextval[i] = next[i];
else
	nextval[i] = nextval[next[i]];

	显然，在注释2处用next数组来回溯j的代码可以用已求得的nextval数组代替（注意，j往前跳，之前的nextval值已经求得），修改后的代码如下：

j = nextval[j];//2

	通过以上的分析，可以将函数的getnext()中的next数组用nextval数组代替掉，最终得到求nextval的代码：

void getnextval(Str substr,int nextval[])
{
	int i = 1,j = 0;//串从数组下标1位置开始储存，因此初值为1
	nextval[1] = 0;
	while(i < substr.length)
    {
		if(j == 0 || substr.ch[i] == substr.ch[j])
        {
			++i;
			++j;
			if(substr.ch[i] != substr.ch[j])
				nextval[i] = j;
			else
			 nextval[i] = nextval[j];
		}
		else
			j = nextval[j];
	}
}