﻿ 萌新也能看懂的KMP算法 - 鸿网互联

# 萌新也能看懂的KMP算法

KMP算法的本质是穷举法,而并不是去创造新的匹配逻辑.

start代表P串在T串中开始匹配的位置,end代表P串与T串对比字符时的位置

``````        String total = "ababcd";
String part = "abc";
total.contains(part);
``````

start=0,end=0;比较T.charAt(0)==P.charAt(0).均为a,此时end右移一位.

start=0,end=1;比较T.charAt(1)==P.charAt(1).均为b,此时end右移一位.

start=0,end=2;比较T.charAt(2)!=P.charAt(2).此时,start右移一位.

start=1,end=0;比较T.charAt(start+end)!=P.charAt(end).此时,start右移一位.

start=2,end=0;比较T.charAt(start+end)==P.charAt(end).此时,此时end右移一位.以此类推.

``````    public static int getIndex(String total, String part) {
char[] totalChars = total.toCharArray();
char[] partChars = part.toCharArray();
int start = 0;
int end = 0;

while (start < total.length()) {
if (totalChars[start + end] == partChars[end]) {
end++;
} else {
start = start + 1;
end = 0;
}
if (end == part.length()) {
return start;
}
}
return -1;
}
``````

T.charAt(start+end)!=P.charAt(end)
T.substring(start,start+end)==P.substring(0,end)

...

① (start,start+end)

② [start+end,...]

T.indexOf(P)的位置只可能出现在这两个区域(因为之前的位置都被排除了).这两个区域的差别是什么呢?

``````    public static int getPublicPart(String part) {
int start = 1;
int end = 0;
char[] chars = part.toCharArray();
while (start < part.length()) {
if (chars[start + end] == chars[end]) {
if (end + start == part.length() - 1) {
return part.substring(start).length();
}
end++;
} else {
start++;
end = 0;
}
}
return 0;
}
``````

end下一次的位置为 P.substring(0,end)的重合度

``````    public static int[] getNext(String part) {
int[] next = new int[part.length()];
int start = 1;
while (start < part.length()) {
next[start] = getPublicPart(part.substring(0, start));
start++;
}
next[0] = -1;
return next;
}
``````

Tips:

KMP算法的本质就是通过穷举end位不匹配时start与end的移动轨迹,来达到复用的效果.

``````    public static int indexOf(String total, String part) {
char[] totalChars = total.toCharArray();
char[] partChars = part.toCharArray();
int[] next = getNext(part);

int start = 0;
int end = 0;
while (start < total.length()) {
if (totalChars[start + end] == partChars[end]) {
end++;
} else {
// 与普通匹配不同的其实就是end位不同时,下一次start与end的位置选择
start = start + end - next[end];
end = Math.max(0, next[end]);
}
if (end == part.length()) {
return start;
}
}
return -1;
}
``````

<