KMP算法

KMP算法有动画，建议下载后观看有这样一个字符串：BBCABCDABABCDABCDABDE我想知道，里面是否包含另一个字符串ABCDABDBBCABCDABABCDABCDABDEABCDABD首先，字符串BBCABCDABABCDABCDABDE的第一个字符与搜索词ABCDABD的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。BBCABCDABABCDABCDABDEABCDABD首先，字符串BBCABCDABABCDABCDABDE的第一个字符与搜索词ABCDABD的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。因为B与A不匹配，搜索词再往后移。BBCABCDABABCDABCDABDEABCDABD就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。接着比较字符串和搜索词的下一个字符.BBCABCDABABCDABCDABDEABCDABD还是相同。BBCABCDABABCDABCDABDEABCDABD直到字符串有一个字符，与搜索词对应的字符不相同为止。BBCABCDABABCDABCDABDEABCDABD这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。BBCABCDABABCDABCDABDEABCDABD这样做虽然可行，但是效率很差，因为你要把搜索位置移到已经比较过的位置，重比一遍。那么我们想什么办法来解决这一问题呢？BBCABCDABABCDABCDABDEABCDABD一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是ABCDAB。KMP算法的想法是，设法利用这个已知信息，不要把搜索位置移回已经比较过的位置，继续把它向后移，这样就提高了效率。怎么利用这个已知信息呢？可以针对搜索词，算出一张《NEXT值表》，即失败指针。这张表是如何产生的，等下再介绍，这里只要会用就可以了。已知空格与D不匹配时，前面六个字符ABCDAB是匹配的。查表可知，字符D对应的“NEXT值为2，因此按照下面的公式算出向后移动的位数：移动位数=已匹配的字符数-对应的NEXT值BBCABCDABABCDABCDABDEABCDABD因为6-2等于4，所以将搜索词向后移动4位。BBCABCDABABCDABCDABDEABCDABD因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（AB），C对应的“NEXT值为0。所以，移动位数=2-0，结果为2，于是将搜索词向后移2位。BBCABCDABABCDABCDABDEABCDABD因为空格与A不匹配，0-(-1)=1，所以继续后移一位。BBCABCDABABCDABCDABDEABCDABD逐位比较，直到发现C与D不匹配。于是，移动位数=6-2，继续将搜索词向后移动4位。BBCABCDABABCDABCDABDEABCDABD逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数=7-0，再将搜索词向后移动7位，这里就不再重复了。下面介绍《NEXT值表》是如何产生的。第一位的next值必定为-1；计算第n个字符的NEXT值：1.查看第n-1个字符对应NEXT值，设为a；3.若不为-1，将第n-1个字符与第a个字符比较4.如果相同，第n个字符对应的NEXT值为a+15.如果不同，令a等于第a个字符的NEXT值，执行第第2步。2.判断a是否为-1，若为-1，则第n个字符next值为0KMP代码实现作NEXT值表：//传入模式串与NEXT的空数组//循环给每一个字符的next赋值KMP部分：END