暴力匹配
暴力匹配算法相对简单，从文本串0索引处依次与模式串比对一旦模式串与文本串不匹配则将文本串索引+1继续依次与模式串对比直到找到匹配字符串或者无匹配。举个例子
文本串：S="BBABBABBABBCC"
模式串：P="BBABBC"
首先P[0]==S[0]继续对比P[1],S[1]。P[1]==S[1]直至P[5]!=S[5] S索引回溯至0+1处即P[0]与S[1],P[1]与S[2],P[2]与S[3],以此类推。一旦P的某个值不与S对应相等S回溯原索引+1处继续对比。直至找到相应字符串，或找不到（暴力匹配不配被单独分析emmm，只是与KMP做个对比）
KMP
可以看到暴力匹配每次发生匹配都要从文本串原索引+1处重新对比
BBABBABBABBCC
BBABBC
//那么当模式串匹配到C字符时匹配失败则需要
BBABBABBABBCC
BBABBC
//通过肉眼可以看到右移一位显然不是最好的选择。D.E.Knuth，J.H.Morris和V.R.Pratt两位大神给出了最佳右移位数的算法。
这里就要引入一个重要的概念了：公共元素 最大公共元素长度
公共元素即当前模式串和文本串以匹配的字符串，最大公共元素有一个固定算法。
以上文为例。首次发生匹配时产生的公共元素即为BBABB下面是最大公共元素长度算法：
将BBABB拆解，
先按前缀拆解可拆为：
B
BB
BBA
BBAB
按后缀拆解为：
B
BB
ABB
BABB
对比按前缀拆解得到的结果和按后缀拆解的结果很容易看出BB元素是相同的，则BB的长度就是最大公共元素长度。仔细考虑下也可以知道为什么要这么分解，匹配失败后得到公共元素如果无法在后缀结果中找到与前缀结果相同的元素那么模式串在该公共元素内不可能找到与之匹配的结果。
得到最大公共元素长度后用公共元素长度减去最大公共元素长度即是匹配失败后文本串需要右移的位数。为什么呢
BBABB为公共元素
最大公共元素为BB，移动匹配如下
BBABBABBABBCC
BBABBC
还是例子比较直观。模式串从公共元素后缀BB开始匹配那公共元素除去BB后缀剩下的就是移动的位数（突然非常敬佩能把问题解释明白的人2333）
好的直接上代码
package com.wxm.string;
import java.util.Arrays;
public class Kmp {
public static void main(String[] args) {
String str = "ACBABABDDABDABABCBCABDDBABAB";
String pattern = "ABABC";
char[] s = str.toCharArray();
char[] p = pattern.toCharArray();
int kmp = kmp(s, p);
System.out.format("\33[1;34m匹配元素起始索引：%d", kmp);
}
public static int kmp(char[] s, char[] p) {
int index = -1;
int sLen = s.length;
int pLen = p.length;
int sIndex = 0;
while (sIndex != sLen) {
int match = 0;
int stempSIndex = sIndex;
//如果查到倒数pLen个字符还没找到匹配就不用继续向后移位了因为s的剩余元素长度小与p不可能找到相匹配的元素
if (stempSIndex + pLen > sLen) {
break;
}
for (char c : p) {
if (c == s[stempSIndex]) {
stempSIndex++;
match++;
} else {
char[] chars = Arrays.copyOfRange(p, 0, match);
int partitionMatch = getMoveStep(chars);
sIndex += partitionMatch;
break;
}
}
//如果匹配长度等于pattern说明已经找到匹配元素
if (match == pLen) {
index = sIndex;
break;
}
}
return index;
}
public static int getMoveStep(char[] chars) {
int len = chars.length;
//最大公共元素长度，从最长的开始试
int times = len - 1;
while (times > 0) {
int match = 0;
for (int i = 0; i < times; i++) {
if (chars[i] == chars[len - times + i]) {
match++;
} else {
break;
}
}
//如果匹配次数等于假定的最大公共元素长度，则说明匹配成功。此时times即是最长公共元素长度
if (times == match) {
break;
}
times--;
}
//使用公共元素长度减最大公共元素长度，即为查找下一次移位需要移动的步数
return len - times;
}
}
//output:匹配元素起始索引：12
网友评论