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

1、第四部分第四部分 字符串字符串制作人：荣誉 BFBF算法设计思想：算法设计思想：将主串的第将主串的第pospos个字符和模式的第个字符和模式的第1 1个字符比较，个字符比较， 若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符； 若若不等不等，从主串的下一字符（，从主串的下一字符（pos+1pos+1）起，重新与第一个字符比较。）起，重新与第一个字符比较。 BF算法算法 （又称古典或经典的、朴素的、穷举的）（又称古典或经典的、朴素的、穷举的） KMP算法算法（特点：速度快）（特点：速度快）算法算法种类：种类：直到主串的一个连续子串字符序列与模式相等直到主串的一个连续子串字符序列与模式相

2、等 。返回值为。返回值为S S中与中与T T匹配的子匹配的子序列序列第一个字符的序号第一个字符的序号，即匹配成功。，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 .0 .S=a b a b c a b c a c b a bT=T=a b c a cpos=5Int Index(SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功子串结束，说明匹配成功 else return0;/Index BFBF算法的实现算法的实现即即IndexIndex（）

3、操作的实现（）操作的实现 （见教材（见教材P79P79） S=a b a b c a b c a c b a bT=T=a b c a cpos=5相当于子串向右滑动一个字符位置相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。配的首个字符位置。i ij j20132013年真题：年真题：KMPKMP算法是模式匹配算法算法是模式匹配算法KMP算法由两部分组成：第一部分，计算模式串的next或nextval数组。第二部分，利用计算好的模式串的nextval数组，进行模式匹配。 KMP算法中有next数组和nextv

4、al数组之分。 他们代表的意义和作用完全一样，完全可以混用。 唯一不同的是，next数组在一些情况下有些缺陷，而nextval是为了弥补这个缺陷而产生的。一、求解一、求解nextnext由上述公式，求模式串S1.j-1中,最大的匹配子串P1.Pk-1=Pj-k+1.Pj-1，其长度k-1，k就是nextj的值。例如，j=6时，abaab最大匹配串是ab=ab,长度2，所以next6=2+1=3算法：next思想： 求模式串的最大匹配串P1.Pk-1，是为了出现不匹配项时，j指针不用回溯到模式串的第一个元素(i指针不动)，只需回溯到j=nextj=k的位置继续匹配。因为P1.Pk-1=Pj-k+

5、1.Pj-1，所以P1.Pk-1和Sj-k+1.Sj-1不需要再比较了，一定相等。直接继续比较Sj和Pk就可以了。next_val改进的地方是aaad，j=3的位置，出现匹配失效，直接返回第1个比较，因为前面均是a，一定不等，不必继续比较了。next_val改进的地方是：求求nextnext的算法的算法public static int next(char t)/ next函数求解 int i = 0, j = -1; int next = new intt.length; next0 = -1; while(i if(j = -1 | ti = tj) +i; +j; nexti = j;

6、else j = nextj; 方法二方法二 求求nextnext步骤：next数组值的程序设计求解方法：首先可以肯定的是第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位 进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到 第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。举例：举例：模式串 a b

7、a a b c a cnext值 0 1 1 2 2 3 1 2步骤参考步骤参考1.前两位必为0，1。2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next值加上1，为2。因为是在第三位实现了其next值对应 的值与第三位的值相同。4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位

8、的a进行比较，相同，则第五位的next值为第二位b的 next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c

9、的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。二、求解二、求解nextvalnextval值值求nextval数组值有两种方法，一种是不依赖next数组值直接用观察法求得，一种方法是根据next数组值进行推理，两种方法均可使用，视更喜欢哪种方法而定。 本文主要分析nextval数组值的第二种方法：模式串 a b a a b c a cnext值 0 1 1 2 2 3 1 2nextval值 0 1 0 2 1 3 0 2过程过程 1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。2.第三位的next值

10、为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.第八位的ne

11、xt值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。 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.第六位的

12、next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。 6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为0。 7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。模式串abaabcacnext值01122312nextval值01021302总结总结 求求nextvalnextval的算法：的算法：(1)第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。(2)若si与s nexti 比较：不同，则nextvali值为

13、其next值;相同，则步骤（3）（3）s nexti 与s nexti nexti 比较:不同，则nextvali值为s nexti nexti 的next值;相同，若nextvali值为0时退出递归，则步骤（3）;三、三、nextnext和和nextvalnextval比较比较Next数组的缺陷举例如下：比如主串是“aab.” 省略号代表后面还有字符。 模式串“aac”通过计算aac的next数组为012（另外，任何字符串的第二位字符的next总是1，因此你可以认为他固定为1）当模式串在字符c上失配时，会跳到第2个字符，然后再和主串当前失配的字符重新比较，即此处用模式串的第二个a和主串的b比

14、较即 aab aac显然a也不等于b。然后 会跳到1，接着比，然后又失配，直到最后才使主串后移一位。而“aac”的nextval数组为002 当在c失配时会跳到2，若还失配就直接跳到0，比next数组少比较了1次。在如果模式串很长的话，那可以省去很多比较，因此你应该使用nextval数组。代码实现代码实现 public static void main(String args) throws IOException/main函数，输入主串和模式串 System.out.print(请输入主串:); Scanner sn1 = new Scanner(System.in); String s1

15、= sn1.next(); System.out.print(请输入模式串:); Scanner sn2 = new Scanner(System.in); String s2 = sn2.next(); char s3 = s1.toCharArray(); char s4 = s2.toCharArray(); System.out.print(KMP_test(s3,s4); public static int KMP_test(char s, char t)/ 主串顺序匹配 int next = next(t); int i = 0, j = 0; while(i if(j = -1

16、| si = tj) +i; +j; else j = nextj; 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 intt.length; next0 = -1; while(i if(j = -1 | ti = tj) +i; +j; nexti = j; else j = nextj; System.out.println(Arrays.toString(next); return next; 对于改进的对于改进的KMPKMP算法，只需要把算法，只需要把nextnext函数换为函数换为nextvalnextval函数就行了函数就行了public static int next(char t) int i = 0, j = -1; int next = new intt.length; next0 = -1; while(i if(j = -1