首页 > 代码库 > BF算法和KMP算法
BF算法和KMP算法
串的模式匹配算法即确定主串中所含子串第一次出现的位置。BF算法是古典的，采用穷举的思想，而KMP算法是模式匹配算法的改进算法。
1.BF算法设计思想：将主串的第pos个字符和模式的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，
重新与第一个 字符比较。直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失
败。
例子：主串s=＂ababcabcacbab＂，模式t=＂abcac＂
BF算法的思想很简单，下边看一下实现：
1.简单的算法
1 public class StringUtil { 2 3 public static int index(String s1, String s2){ 4 char[] c1 = s1.toCharArray(); 5 char[] c2 = s2.toCharArray(); 6 int i=1; //表示从第一个位置开始匹配 7 int j=1; 8 while(i<=c1.length&& j<=c2.length){ 9 if(c1[i-1]==c2[j-1]){ //下标从0开始10 i++;11 j++;12 }13 else{14 i=i-j+2; //相当于向右移动一个字符的位置15 j=1; //子串j回到首位，重新开始匹配16 }17 }18 return i-c2.length; //返回匹配成功的首字母位置 19 }20 }
这种算法的时间复杂度，用n和m分别表示主串和模式串的长度，有的情况下是O(n+m);但最坏的情况下的时间复杂度O(n*m);
2,KMP算法
2.1KMP算法的设计思想
kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法），算法的
思想相比传统的BF算法有点复杂，用了很长时间才理解清楚，有趣的是看到调侃BF和KMP分别解释成“Boyfriend”和“看毛片”，玩笑归玩笑，无巧不成书啊。
思想：能否利用已经部分匹配的结果而加快模式串的滑动速度？ 能！而且主串S的指针i不必回溯！可提速到O(n+m)！
下图是一个简单的例子
从上面的例子中可以看到 i 值不会减小，所以只用考虑 j 的值了，那么需要思考下面两个问题：
1. 如何“记忆”部分匹配结果？
2. 如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k
由上图看到模式串 T 与 主串 S 匹配时在 i = 3出失配，然后i不回朔然后 T 串向右移动到i=3处，j 由3变为1，然后又在在i=7处失配，
继续右移，此时j（k位置）由5变成2，
i
S=‘a b a b c a b c a c b a b’ 设目前应于T的第k个字符进行比较，则T的1~k-1位=S前 i-（k-1）~ i-1位
T=‘a b c a c’
k
___________________________________
i
S=‘a b a b c a b c a c b a b’
T=‘a b c a c’ 刚才肯定是在S的i处和T的第j字符 处失配,则S前i-(k-1)～i-1位＝T的j-(k-1)～j-1位
k
两式联立可得：‘T1…Tk-1’=‘Tj-(k-1) …Tj-1’.
把T中各个位置的j的之变化定义为一个next数组，一旦失配，应从模式串T中第next[ j ]个字符开始与S的失配点i 重新匹配!
怎样计算模式T所有可能的失配点 j 所对应的 next[j]
例： 模 式 串 T：‘ a b a a b c a c ’
可能失配位 j： 1 2 3 4 5 6 7 8
新匹配位 next[j] : 0 1 1 2 2 3 1 2
j=1时, next[ j ]≡ 0；因为属于“j=1”;
j=2时, next[ j ]≡ 1；（由 1 到 j-1 只有 一个字符）因为属于“其他情况”；
j=3时, 由 1 到 j-1的字符串只有‘ab’，属于其他情况
j=4时，由 1 到 j-1，‘aba‘看到 T1 = T3(即a) k=2 即属于第二种情况，next[j]=2,
j=5时，由1到j-1，‘abaa’ T1=T4同上 k=2，
......
对上边的传统算法的图用KMP算法改进如下：
算法实现：
1 public static int IndexKMP(String S,String T){ 2 3 int i=0; int j=-1; 4 int[] next=getNext(T); 5 6 while(i<S.length()&&j<T.length()){ 7 8 if(j==-1||S.charAt(i)==T.charAt(j)){ 9 i++;10 j++;11 }12 else {13 j=next[j];14 }15 }16 if(j==T.length()){ //下标从0开始，+1这里返回的是位置17 return i-j+1; }18 return -1;19 }
得到next数组的方法
1 public static int[] getNext(String T){ 2 int j=-1; 3 int i=0; 4 int next[]=new int[T.length()+1]; 5 next[0]=-1; 6 while(i<T.length()){ 7 if(j==-1||T.charAt(i)==T.charAt(j)){ 8 j++; 9 i++;10 next[i]=j;11 } else {12 j=next[j];13 }14 }15 return next;16 }
KMP算法的时间复杂度：由于指针i无须回溯，比较次数仅为n,即使加上计算next[j]时所用的比较次数m，比较总次数也仅为n+m=O(n＋m)，大大快于BF算法。
BF算法和KMP算法