关于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(i<strLen&&j<subLen){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(i<strLen){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≤pos<StrLength(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=aji

1<=i,j<=nk=0

1

2

3

4

5

6

n(n+1)/2-1

对称矩阵元素可以只存储下三角部分，共需n(n+1)/2个单元的空间(三角矩阵的存储方式类似）

以一维数组sa[0..n(n+1)/2-1]作为n阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置sa[k]之间关系：

k=0

1

2

3

4

5

6

n(n+1)/2-1

例如：a42在sa[]中的存储位置是：

k=4*(4+1)/2+2=12

sa[12]=a42

带状矩阵所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个（左上角与右下角补上0后，最后必须减掉），如下图怕示：为计算方便，认为每一行都有2d+1个非0元素，若少则0补足存放矩阵的数组sa[]有:n(2d+1)个元素数组，元素sa[k]与矩阵元素aij之间有关系:

k=i*(2d+1)+d+(j-i)（第一项i*(2d+1)表示前i行一共有几个元素，d+(j-i)这一项是用来确定第i行中，第j列前有几个元素，以i=j时，这时j-i=0，这个作为“分水岭“，左右两边的元素分别加上偏移量d。）本例：d=1K=0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

（a0前以及a14处放一个0是用来表示在矩阵的左上角及右下角补上的0）稀疏矩阵：行数m=6,

列数n=7,

非零元素个数t=6稀疏矩阵(SparseMatrix)的抽象数据类型

template

<class

Type>

class

SparseMatrix

{

int

Rows,

Cols,

Terms;

//行/列/非零元素数

Trituple<Type>

smArray[MaxTerms];

public:

//三元组表

SparseMatrix

(

int

MaxRow,

int

Maxcol

);

SparseMatrix<Type>

Transpose

(

);

//转置

SparseMatrix<Type>

//相加

Add

(

SparseMatrix<Type>

b

);

SparseMatrix<Type>

//相乘

Multiply

(

SparseMatrix<Type>

b

);

}

A的三元组顺序表图示

三元组(Trituple)类的定义template<class

Type>

class

SparseMatrix<Type>;template<class

Type>

class

Trituple

{

friend

class

SparseMatrix

<Type>

private:

int

row,

col;

//非零元素所在行号/列号

Type

value;

//非零元素的值

}

稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置：

a.smArray

b.smArray（a.Rows=6,a.Cols=7,a.Terms=8）

（b.Rows=7,b.Cols=6,b.Terms=8）

稀疏矩阵转置算法思想对应上图的一个最简单的方法是把三元组表中的row与col的内容互换，然后再按照新的row中的行号对各三元组从小到大重新排序，最后得到上图右半部分的三元组表，但是用这样的方法其时间复杂度为平方级的，下面再用一种方法来处理：假设稀疏矩阵A有n列，相应地，需要针对它的三元组表中的col列进行n次扫描，第k次扫描是在数组的col列中查找列号为k的三元组，若找到，则意味着这个三元组所表示的矩阵元素在稀疏矩阵的第k列，需要把它存放到转置矩阵的第k行。具体办法是：取出这个三元组，并交换其row（行号）与col（列号）的内容，连同value中存储的值，作为新三元组存放到矩阵的三元组表中。当n次扫描完成时，算法结束。程序清单如下：稀疏矩阵的转置template

<class

Type>

SparseMatrix

<Type>

SparseMatrix

<Type>::

Transpose

(

)

{//将稀疏矩阵a(*this指示)转置，结果在稀疏矩阵b中。

SparseMatrix<Type>

b

(

Cols,

Rows

);//创建一个稀疏矩阵类的对象b

b.Rows

=

Cols;

b.Cols

=

Rows;

//交换其row（行号）与col（列号）的内容，连同valueb.Terms

=

Terms;//中存储的值作为新三元组放到矩阵的三元组表中。

if

(

Terms

>

0

)

{

//非零元个数不为零

int

CurrentB

=

0;

//转置三元组表存放指针for

(

int

k

=

0;

k

<

Cols;

k++

)

//按列号做扫描，做cols次

for

(

int

i

=

0;

i

<

Terms;

i++

)

//在数组中找列号为k的三元组

if

(

smArray[i].col

==

k)

{

//第i个三元组中元素的列号为k

b.smArray[CurrentB].row

=

k;

//新三元组的行号

b.smArray[CurrentB].col=smArray[i].row;//新三元组的列号

b.smArray[CurrentB].value=smArray[i].value;//新三元组的值

CurrentB++;

//存放指针加1

}

}

return

0;

}

若设稀疏矩阵的行数为Rows，列数为Cols，非零元素个数为Terms，则最坏情况下的时间复杂度主要取决于二重潜套for循环内的if语句，if语句在二重循环的作用下总的执行次数为O（Cols*Terms）。而在if控制内的赋值语句则执行了Terms次，它取决于三元组表本身的长度。若非零元素个数Terms与矩阵行，列数的乘积Rows*Cols等数量级，则上述程序清单的时间复杂度为O(Cols*Terms)＝O（Rows*Cols*Cols）。设Rows=500,Cols=100,Terms=10000,则O(500*100*100)=O(5000000)，处理效率极低。为了提高转置效率，采用一种快速转置的方法。在此方法中，引入两个辅助数组：1．

rowSize[]。用它存放事先统计出来的稀疏矩阵各列的非零元素个数，转置以后是转置矩阵各行的非零元素个数。具体做法是：先把这个数组清零，然后扫描矩阵A的三元组表，逐个取出三元组的列号col，把以此列号为下标的辅助数组元素的值累加1。for(inti=0;i<Cols;i++)rowSize[i]=0;//清零

for(j=0;j<Terms;j++)rowSize[smArray[j].col]++;//统计，注意这里用到的简洁的算法2．

rowstart[]。用它存放事先计算出来的稀疏矩阵各行非零元素在转置矩阵的三元组表中应存放的位置。rowSize[0]=0;//计算矩阵b第i行非零元素的开始存放位置for(i=1;i<Cols;i++)rowStart[i]=rowStart[i-1]+rowSize[i-1]快速转置算法的思想Ø

建立辅助数组rowSize和rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。Ø

扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查rowStart表，按查到的位置直接将该项存入转置三元组表中。Ø

转置时间代价为O(max(Terms,Cols))。若矩阵有200列，10000个非零元素，总共需要10000次处理。对应上图的代码在就像前面所列的：

for(inti=0;i<Cols;i++)rowSize[i]=0;

for(i=0;i<Terms;i++)

rowSize[smArray[i].col]++;

rowStart[0]=0;

for(i=1;i<Cols;i++)

rowStart[i]=rowStart[i-1]+rowSize[i-1];

稀疏矩阵的快速转置template

<class

Type>

SparseMatrix<Type>SparseMatrix<Type>::FastTranspos

(

)

{//对稀疏矩阵a(*this指示)做快速转置，结果放在b中，时间代价为O(Terms+Columns)。

int

*rowSize

=

new

int[Cols];//辅助数组，统计各列非零元素个数

int

*rowStart

=

new

int[Cols];//辅助数组，预计转置后各行存放位置

SparseMatrix<Type>

b

(

Cols,

Rows

);//存放转置结果

b.Rows

=

Cols;

b.Cols

=

Rows;