数据结构》课件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
显示全部