2014计算机考研临考指导:数据结构常用算法精析4
数据结构是计算机考研408计算机学科专业基础综合的重要组成部分，考生需要认真复习，尤其是对于数据结构中一些常用的算法问题，考生一定要弄懂弄会，理解的去掌握，下面是第4章节有关数据结构算法，希望对大家有所帮助。第四章
KMP算法和朴素的匹配算法的关键区别就是解决了主串指针i的回溯，原理如下
设主串S[]和模式串T[],如比较到模式串的第j个字符。 当主串指针i和模式串指针j比较时 ，说明他们前面的所有字符都已经对应相等了。而
Next=k的定义是T1T2…Tk-1==Tj-k+1Tj-k+2….Tj-1且k是最大了，没有更长的了。
所以Si和Tj比较失败时Si和Tk去比较。不可能有 这种匹配的成功，因为S2S3…..Si-1= =T2T3……Tj-1,而T2T3….Tj-1是不等于T1T2….Tj-2。除非next=j-1;因为next定义的是最长的。所以任何挪动小于next的串的匹配都是不能成功的。直到Tnext和S相比是才是最早有可能成功的。
Int KMP_Index(Sstring S,Sstring T,int pos)
{
i=pos;j=1;
while(i
{
If(j=0||S=T)//j=0表示模式串已经退到起点了说明在这个位置彻底不可能了，
{ ++i; ++j; } //i必须下移,j回到1开始
Else j=next;
}
If(j>T) return i-T;
Else return 0;
}
求next的方法和原理
设k=next;那么T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1;
若Tj= =Tk,那么T1T2…Tk-1Tk= =Tj-k+1……Tj-2Tj-1Tj;
所以 next=k+1=next+1;且T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1已经是
最长的序列，所以k+1也是next最长的
若Tj不等于Tk,那么就需要重找了。即…..Tj-1Tj ?,
T1T2….
所以next首先=k=next; 即…..Tj-1Tj ?,
T1T2…Tk-1.
若不相等，则next=next; 即…..Tj-1Tj ?,
T1T2….Tnext-1
直到找到这样的序列， 即…..Tj-1Tj ?,
T1T2 ...To
那么，next=next]=next]]…..=o+1;
Void get_next(Sstring T,int next[])
{
i=1; next=0; j=0;//i表示当前求的next
While(i
{
if(j=0 | | T=T)
{
++i;
++j;
next=j;
}
Else j=next;
}
}
因为 next[ ] 在匹配过程中，若T[ j ]=T[ next ];那么当 S不等于T,
S[ i]肯定也不等于T ];
所以 S应直接与T]比较，而我们通过将next修正
为nextval=next];这样能使比较更少。
Void get_nextval(Sstring T,int nextval[])
{
i=1; nextval=0; j=0;
while(i
{
if(j=0 || T= T)
{
++i;
++j;
if(T!=T) (责任编辑：tq2013)
页:
[1]