ky3-串-数据结构考研课件-大连海事大学.ppt

第四部分 字符串;① BF算法设计思想： 将主串的第pos个字符和模式的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。 ;Int Index(SString S, SString T, int pos) { i=pos; j=1; while ( i=S[0] j=T[0] ) { if (S[i] = = T[j] ) {++i, ++j} //继续比较后续字符 else {i=i-j+2; j=1;} //指针回溯到 下一首位，重新开始匹配 } if(jT[0]) return i-T[0]; //子串结束，说明匹配成功 else return0; }//Index;2013年真题：;KMP算法是模式匹配算法;一、求解next;aaad，j=3的位置，出现匹配失效， 直接返回第1个比较，因为前面均是a，一定不等，不必继续比较了。;求next的算法;方法二 求next;举例：;步骤参考;二、求解nextval值;过程; 1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。 2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三位的nextval值为0。 3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。 4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，为1。 5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。 6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为0。 7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。;总结 求nextval的算法：;三、next和nextval比较;代码实现;public static int KMP_test(char [] s, char [] t){// 主串顺序匹配 int [] next = next(t); int i = 0, j = 0; while(i if(j == -1 || s[i] == t[j]){ ++i; ++j; }else{ j = next[j]; } } System.out.println(i); if(j return 0; }else{ return i-t.length; } };public static int [] next(char [] t){// next函数求解 int i = 0, j = -1; int [] next = new int[t.length]; next[0] = -1; while(i if(j == -1 || t[i] == t[j]){ ++i; ++j; next[i] = j; } else j = next[j]; } System.out.println(Arrays.toString(next)); return next; };对于改进的KMP算法，只需要把next函数换为nextval函数就行了;例子:;感谢您的观看 Thank you for watching