数据结构与c++算法设计案教程课件数据结构与c++算法设计案例教程课件数据结构与c++算法设计案例教程课件数据结构与c++算法设计案例教程课件.ppt

一旦失配，应从模式串T中第next[ j ]个字符开始与S的失配点i重新匹配。 next[ j ]＝ 0 当j＝1时 max { k |1kj 且‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’ } 1 其他情况 图5-6 next[j]的求解 推算模式串“a b a a b c a c”的next函数值如下： j=1时, next[ j ]≡ 0；因为属于“j=1”; j=2时, next[ j ]≡ 1；因为属于“其他情况”； j=3时, k={2}，只需查看‘T1’=‘T2’； j=4时, k={2，3}，要查看‘T1’=‘T3’ 和‘T1T2’=‘T2 T3’ j=5时, k={2，3，4}，要查看‘T1’=‘T4’ 、‘T1T2’=‘T3T4’ 和‘T1T2T3’=‘T2T3T4’ 由上面的求解可得到如下的next的求解值。 可能失配位 j： 1 2 3 4 5 6 7 8 模 式 串 T： a b a a b c a c 新匹配位 next[j] : 0 1 1 2 2 3 1 2 KMP算法在形式上与简单模式匹配算法极为相似，不同之处仅在于当匹配过程产生失败时，指针i不变，指针j退回到next[j]所指示的位置上重新进行比较，并且当指针j退回到0时，指针i和指针j需要同时增1。 下面给出串的最基本几个算法 char str1[100],str2[100]; void AdressString::StrIndex(char str1[],char str2[]) //在str1[]中寻找与str2[]一样的字符串,显示所在的位置,没有则显示无此串, //用简单模式匹配算法实现(重要) { int i=0,j=0; while(istrlen(str1) jstrlen(str2)) //用while循环进行匹配 { if(str1[i]==str2[j]) //如果当前字符相同,则继续惊醒比较 { i++; j++; } else //否则,则从开始位置的下一位置进行比较 { i=i-j+1; j=0; } } if(j==strlen(str2)) //j==strlen(str2)匹配成功 { coutstr1中包含str2!endl; cout位置为(从0开始): i-jendlendl; } else coutstr1中不包含str2!endlendl; //jstrlen(str2,)匹配不成功 } 用简单模式匹配算法实现在str1[]中寻找与str2[]一样的字符串并显示所在的位置,没有则显示“无此串”。首先，定义两个初始值为0的变量i、j，分别标记str1与str2的下标。然后，从两个字符串的开始位置，逐个匹配。若匹配成功，则i和j同时加1，否则，i赋值为开始匹配成功字符的下一个字符，j重新赋值为0。直到循环条件不成立为止。最后，判断变量j的值，若j==strlen(str2)说明匹配成功了str2中的所有字符，所在位置为i－j。 void AdressString::StrKMP(char str1[],char str2[]) //在str1[]中寻找与str2[]一样的字符串,显示所在的位置,没有则显示无此串, //用KMP算法实现(重要) { int i=0,j=0,next[100]; while(istrlen(str1) jstrlen(str2)) { if(str1[i]==str2[j]) //如果当前字符相同,则继续进行比较 { i++; j++; } else j=getnext(next); } couti= iendl; if(j==strlen(str2)) //j==strlen(str2)匹配成功 { StrIndex(str1,str2); } else coutstr1中不包含str2!endlendl; //jstrlen(str2),匹配不成功 } 用KMP算法实现在str1[]中寻找与str2[]一样的字符串并显示所在的位置,没有则显示无此串。首先，定义两个初始值为0的变量i、j，分别标记str1与str2的下标。然后，从两个字符串的开始位置，逐个匹配。若匹配成功，则i和j同时加1，否则，i值不变，j使用函数getnext(ne