字符精确匹配算法bf、kmp、bm、sunday、rk

字符精确匹配算法bf、kmp、bm、sunday、rk

bf算法

算法详解

bf算法又称暴力匹配算法，暴力匹配的思路是：从头开始，一个一个的去匹配，每匹配成功一个字符，偏移量（模式串的下标）加1，直到超出文本串或模式串的范围或失配情况，超出文本串范围时说明文本串不存在模式串，超出模式串范围时说明匹配成功，失配情况则将偏移量置0，文本串的下标加1。看下图有助于理解：

算法代码

    /*** 暴力匹配算法*/public int violentSearch(String text, String pattern){int res = -1;if (text == null || pattern == null){return res;}char[] s = text.toCharArray();char[] p = pattern.toCharArray();// i=>s,,j=>p,j也可以看成是偏移量int i = 0, j = 0;while (true){if (i+j>=s.length || i<0){break;} else if (j>=p.length || j<0){res = i;break;} else if (s[i+j] == p[j]){j++;} else {i++;j = 0;}}return res;}

kmp算法

算法详解

kmp算法是在暴力匹配算法上做的一个优化，它是根据模式串的特征来生成一个next数组，在每次字符失配的时候，根据next数组中的值来跳转，而不是直接跳转到模式串的开头。
1、next函数详解
在很多地方都会通过字符串的前缀和后缀来推导next函数，我刚开始的时候也是一直琢磨着那些文章（比如阮一峰的kmp文章），可能因为我的思维跟他们不一样吧，所以理解很痛苦，所幸最后还是读懂了他们的思路。下面我以我的思路来详解一下next函数：next数组的前两位值永远是[-1,0]，后续next值的将会根据前面的字符和next值来求，详解看图。

2、next函数详解----优化版
上述求解的next[j]的值是跟第j个字符没有任何关系的，所以好多大佬都会做个优化。这里以我的思路来讲，优化就是在用上述方式求出值后，判断当前字符是否和当前next值指向的字符相等，若相等则当前的next值变为当前next值指向的位置的next值，如图。当然，在实际写的时候稍微优化一下。

算法代码

    /*** kmp算法的next数组求解*/private int[] getNext(char[] str) {if (str == null) {return null;}switch (str.length) {case 0:return new int[]{};case 1:return new int[]{-1};case 2:return new int[]{-1,0};default:break;}int[] next = new int[str.length];next[0] = -1;next[1] = 0;// j是字符的序号，k是j-1字符的next值int j=2,k=0;while (j<str.length){if (k==0 || str[j-1] == str[k]){next[j] = (str[j-1] == str[k])?++k:0;j++;} else {k = next[k];}}return next;}/*** kmp算法的next数组求解--优化版*/private int[] getNextVal(char[] str) {if (str == null) {return null;}switch (str.length) {case 0:return new int[]{};case 1:return new int[]{-1};case 2:return new int[]{-1,0};default:break;}int[] next = new int[str.length];next[0] = -1;next[1] = 0;// j是字符的序号，k是j-1字符的next值int j=2,k=0;while (j<str.length){if (k==0 || str[j-1] == str[k]){next[j] = (str[j-1] == str[k])?++k:0;// 如果j和next[j]的字符相等，则把next[j]值替换为next[ next[j] ]，否则保留原值，k将记录原值if (str[ next[j] ] == str[j]) {next[j] = next[ next[j] ];}j++;} else {k = next[k];}}return next;}/*** 字符串匹配的kmp算法*/public int kmpSearch(String text, String pattern) {int i=0,j=0;char[] s = text.toCharArray();char[] p = pattern.toCharArray