数据结构》课件C语言04.ppt

* 示例6 设模式串P=`abaabcac`，则可得如下之next函数值 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next [j] 0 1 1 2 2 3 1 2 注1. 必有next[j]j. 注2. Next[j]（即k）值只取决于模式串p本身，而与目标串S无关系 令next[j]=k， next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。这是一个函数关系，称作模式串的next函数。由前述的讨论知： * 示例7 利用模式的next函数进行匹配的过程 S=`acabaabaabcacaabc` P=`abaabcac` 第一趟匹配 acabaaba··· ab next[2]=1 第二趟匹配 acabaaba··· a next[1]=0 第三趟匹配 acabaabaab··· abaabc next[6]=3 第四趟匹配 acabaabaabcacaabc··· abaabcac 匹配，得序号index(s,p)=i-length(p)=14-8=6. ↓i=2 ↑j=2 ↑j=1 ↑j=1 ↑j=6 ↑j=3 ↑j=9 ↓i=2 ↓i=3 ↓i=8 ↓i=8 ↓i=14 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next [j] 0 1 1 2 2 3 1 2 ?求模式串的next函数 基于next函数的匹配移位规则： 设i,j分别指示主串和模式串中正待比较的字符，初值i=1,j=1. 1) 若Si=Pi，则i,j分别加1，返至1)； 2) 若Si≠Pi，则j退到next[j]位置再比较， a.当j0，则返至1)； b.当j=0（即模式的第一个字符“失配”），则令i加1，j加1（即j=1），返至1)； 如此继续，直至匹配成功(jlength(t))，并进而获得定位序号，或者匹配失败(ilength(s)而j≤length(t)). * ?求模式串的next函数 KMP算法的实现 int index_KMP( SString s, SString t ) { //利用模式串的next函数求模式串t在主串S中位置的KMP算法 i = 1; j = 1; //指针初始化 while((i≤length(s)) (j≤length(t))) if((j==0)||(s[i]==t[j])) {i++;j++} //继续下一对字符的比较 else j = next[j]; //模式串向右滑动 if( j length(t)) return(i-length(t)); //匹配成功 else return(0); } //index_KMP 算 法 4.5 * * 注1. KMP算法是在已知模式串的next函数值的基础上执行的，故其前提是假定已有求得模式串的next函数值的算法。 注2. 算法中j=0表明Si与P1就不匹配，故令i加1，j加1(0+1=1)，即令Si+1与P1继续比较。 注3. 算法分析（时间复杂度）：(1)该算法执行过程中i只增不减，由i初值为1，循环过程中保持i≤n，所以循环体中i++最多执行n次；（2）另外j的初值为1，而循环体中保持j0. 由于next[j]j，所以j=next[j]的最多执行次数也不超过n. 故上述算法的时间复杂度为O(n)。 算法思想 可以从分析其定义出发，用递推的方法求得next函数。 1)由定义知 next[1]=0