关于KMP算法当中的next函数

关于KMP算法当中的next函数首先先贴出KMP算法的框架代码，这段代码使用C语言当中的字符串数据结构，因此字符串当中第一个字符的下标为零。intIndex(constchar*str1,constchar*str2,intpos){int*nextFunc=get_next(str2);intstrLen=strlen(str1);intsubLen=strlen(str2);inti=pos,j=0;while(istrLen&&jsubLen){if(j==-1||str1[i]==str2[j]){i++;j++;}elsej=nextFunc[j];}if(j==subLen)returni-subLen;return-1;}相比较那种最简单的算法而言这里的神奇之处在于一个next函数，由于这个next函数的存在导致我们在模式匹配过程当中某个字符出现失配的情况时不再需要回溯主串当中的指针i到开始匹配时的位置。所有的数据结构或者算法的书都告诉我们说，之所以不需要回溯这个i指针是因为在匹配过程当中产生了一些附加的信息，利用这些附加信息就可以得到这样的性能改进。首先我们必须搞清楚这个神奇的next函数的含义。next[j]=k这样一个式子表示的含义是，当主串当中第i个元素与模式串当中第j个元素不匹配时我们应该保持i指针不动而将模式串当中的j指针移动到k这个位置，然后再比较主串的第i个元素与模式串的第k个元素是否匹配，匹配当然没话说照最传统的算法移动两个指针比较下一个元素或者得到完全匹配的结果，不匹配那么再做那个动作，也就是求next[k]=？，然后再比较。之所以存在这么一个next函数是因为，如果说主串与模式串在匹配过程当中主串的第i个元素与模式串的第j个元素不同，那么隐含的意义是主串的从第i-j+1个元素到第i-1个元素与模式串的第1个元素到第j-1个元素是相同的。那么如果说这样不能达到最后全部匹配的结果也就是上面讲的主串[i]!=模式串[j]，那么我们应该从主串的i-j+1到i-1这个字串当中从后到前寻找一个最大子串与模式串的第1到j-1这个字串的从第一个到某个元素的最大子串完全匹配。而我们又知道主串中第i-j+1个元素到第i-1个元素的子串事实上就是模式串当中第1个元素到第j-1个元素所形成的子串。next函数所完成的工作就是这个寻找匹配的工作，他的返回值就是这个子串的最后一个元素的下一个位置。为什么是这个位置，前面讲的很清楚，就是说既然前面那一串匹配，那么接下来要比较的就是这个位置的元素。下面开始描述next函数的求法。从上面的描述我们可以知道next函数的值完全只与模式串相关而与主串是什么样子的没有任何关系，因此对于每个模式串来说都有一个唯一的next串值。求法是这样：如果next[j]=k也就是说模式串的第1个元素到第k个元素与第j-k+1个元素到第j-1个元素相等(可以按照上面的方法推出到主串上哪几个元素)，而且有模式串[j]==模式串[k]那么可以得到next[j+1]=k+1(这里的原理显而易见)；如果不等那么就求另外一个最大子串，方法就是j=next[k]，然后再回到上面的比较。而其他的情况就视作next值为0(事实上只有j=1时的next值才会出现，所以next值的前两个元素固定是0和1)。具体算法如下：int*get_next(constchar*str){intstrLen=strlen(str);int*nextFunc=newint[strLen];if(!nextFunc)return0;nextFunc[0]=-1;inti=0,j=nextFunc[i];while(istrLen){if(j==-1||str[i]==str[j]){i++;j++;nextFunc[i]=next[i-1]+1;}elsej=nextFunc[j];}returnnextFunc;}个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊：KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。一.简单匹配算法先来看一个简单匹配算法的函数：intIndex_BF(charS[],charT[],intpos){/*若串S中从第pos(S的下标0≤posStrLength(S))个字符起存在和串T相同的子串，则称匹配成功，返回第一个这样的子串在串S中的下标，否则返回-1*/inti=pos,j=0;while(S[i+j]!='/0'&&T[j]!='/0')if(S[i+j]==T[j])j++;//继续比较后一字符else{i++;j=0;//重新开始新的一轮匹配}if(T[j]=='/0')returni;//匹配成功返回下标elsereturn-1;//串S中(第pos个字符起)不存在和串T相同的子串}//Index_BF此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。即从j=0起比较S[i+j]与T[j]，若相等，则在主串S中存在以i为起始位置匹配成功的可能性，继续往后比较(j逐步增1)，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的匹配，即将串T向后滑动一位，即i增1，而j退回至0，重新开始新一轮的匹配。例如：在串S=”abcabcabdabba”中查找T=”abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1]和T[1]是否相等…我们发现一直比较到S[5]和T[5]才不等。如图：当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标3。如图：二.KMP匹配算法还是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5]和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==’d’的模式函数值（next[5]=2，为什么？后面讲），直接比较S[5]和T[2]是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。。。最终在S中找到了T。如图：KMP匹配算法和简单匹配算法效率比较，一个极端的例子是：在S=“AAAAAA…AAB“(100个A)中查找T=”AAAAAAAAAB”,简单匹配算法每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1，继续比较。如果使用KMP匹配算法，就不必回溯.对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为O(m+n)，因此在多数的实际应用场合下被应用。KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。看前面的例子。为什么T[5]==’d’的模式函数值等于2（next[5]=2），其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同，且T[5]==’d’不等于开始的两个字符之后的第三个字符（T[2]=’c’）.如图：也就是说，如果开始的两个字符之后的第三个字符也为’d’,那么，尽管T[5]==’d’的前面有2个字符和开始的两个字符相同，T[5]==’d’的模式函数值也不为2，而是为0。前面我说：在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5]和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==’d’的模式函数值，直接比较S[5]和T[2]是否相等。。。为什么可以这样？刚才我又说：“（next[5]=2），其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同”。请看图：因为，S[4]==T[4]，S[3]==T[3]，根据next[5]=2，有T[3]==T[0]，T[4]==T[1]，所以S[3]==T[0]，S[4]==T[1]（两对相当于间接比较过了），因此，接下来比较S[5]和T[2]是否相等。。。有人可能会问：S[3]和T[0]，S[4]和T[1]是根据next[5]=2间接比较相等，那S[1]和T[0]，S[2]和T[0]之间又是怎么跳过，可以不比较呢？因为S[0]=T[0]，S[1]=T[1]，S[2]=T[2]，而T[0]!=T[1],T[1]!=T[2],==S[0]!=S[1],S[1]!=S[2],所以S[1]!=T[0],S[2]!=T[0].还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊情况啊。假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0]间接比较过了，不相等，接下来去比较S[3]和T[0]吧。假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？（本文中next值、模式函数值、模式值是一个意思。）矩阵:矩阵是数值程序设计中经常用到的数学模型，它是由m行和n列的数值构成（m=n时称为方阵）。在用高级语言编制的程序中，通常用二维数组表示矩阵，它使矩阵中的每个元素都可在二维数组中找到相对应的存储位置。然而在数值分析的计算中经常出现一些有下列特性的高阶矩阵，即矩阵中有很多值相同的元或零值元，为了节省存储空间，需要对它们进行压缩存储，即不存或少存这些值相同的元或零值元。操作：可以对矩阵作加、减、乘等运算。存储压缩目标：节约存储空间压缩的方法：零元不存储多个值相同的只存一个压缩存储的对象：稀疏矩阵特殊矩阵特殊矩阵：值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例:对称矩阵、上（下）三角矩阵都是特殊矩阵特殊矩阵压缩存储(以对称矩阵为例)对称矩阵是满足下面条件的n阶矩阵:aij=aji1=i,j=nk=0123456n(n+1)/2-1对称矩阵元素可以只存储下三角部分，共需n(n+1)/2个单元的空间(三角矩阵的存储方式类似）以一维数组sa[0..n(n+1)/2-1]作为n阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置sa[k]之间关系：k=0123456n(n+1)/2-1例如：a42在sa[]中的存储位置是：k=4*(4+1)/2+2=12sa[12]=a42带状矩阵所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个（左上角与右下角补上0后，最后必须减掉），如下图怕示：为计算方便，认为每一行都有2d+1个非0元素，若少则0补足存放矩阵的数组sa[]有:n(2d+