前提：

假设我们在字符串 “bacbababaabababca”中搜寻字符串 “abababca”是否存在。

下面就KMP算法的匹配过程进行阐述。

step0 ：在执行匹配之前，先定义几个概念：“前缀集合”，”后缀集合”，”部分匹配值”

“前缀集合”指除了最后一个字符外，一个字符串的全部头部组合； “后缀集合”指除了第一个字符外，一个字符串的全部尾部组合。 “部分匹配值”指”前缀集合”与”后缀集合”的最长公共元素的长度

举个例子，如字符串 “a”，前缀集合用prefixes表示（下同），按照定义除了最后一个字符，则为空，所以prefixes={}，后缀集合用suffixes表示（下同），按照定义除了第一个字符也为空，即suffixes={}，所以集合 prefixes与 suffixes交集也为空，两个集合的公共元素的长度(即部分匹配值)为0，我们称”a”的部分匹配值为0
再比如字符串 “abab”，则prefixes = {“a”,”ab”,”aba”},suffixes={“b”,”ab”,”bab”}，则前缀集合与后缀集合的交集：{ ”ab“} ，长度为2，即”abab”的部分匹配值为2

3.有些字符串比较特别如 “ababa”，其prefixes={“a”,”ab”,”aba”,”abab”}，suffixes={“a”,”ba”,”aba”,”baba”}，这时候prefixes与suffixes的交集就变成了 {“a”,”aba”}，公共元素有两个，这个时候部分匹配值我们取最大的元素”aba”,长度为3

这样我们就能得到字符串“abababca”的部分匹配表

      char:  | a | b | a | b | a | b | c | a |
      index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
      value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

下面开始ＫＭＰ算法的字符串匹配过程

step1-首先从第一位进行字符串比较:

bacbababaabababca
abababca

可以看到b 与a 并不相等，此时我们直接后移一位

step2-第三个字符“c”时候不匹配

bacbababaabababca
abababca

这个时候已经匹配了字符“a”，按照部分匹配表，其部分匹配值为0，
这个时候后移动位数= 已经匹配的字符数-已经匹配的字符对应的部分匹配值 = 1 - 0 = 1

step3-而移动后的:

bacbababaabababca
abababca

c与a 又不相等，继续移动直到

step4-

bacbababaabababca
abababca

这次的匹配直到a 与b字符不相等，这个时候已经匹配的字符为“ababa”，长度为5，“ababa”对应的部分匹配值通过查表为3

后移位数= 已经匹配的字符数-已经匹配字符对应的部分匹配值 = 5-3 = 2

step5-移动得到

bacbababaabababca
abababca

这个时候后移位数 = 3-1 =2

step6- 再次移动后

bacbababaabababca
abababca

只匹配了a之后又不匹配，则按照匹配表又往后移动一位

step7- 这个时候：

bacbababaabababca
abababca 发现字符串全部匹配，至此匹配结束

总结

如果字符串发生了匹配，那么根据部分匹配表进行的后移之后一定会让字符串的首字母再匹配（有可能会从首字母开始匹配多个），后移位数完全取决于查找的字符串，跟需要被查找的字符串没有关联。

下面附上 KMP算法的java代码实行 Download here

package com.util;
 
import org.apache.log4j.Logger;
 
/**
 * @author ycx
 *
 */
public class KMPStringMatcher {
	private static final Logger logger = Logger
			.getLogger(KMPStringMatcher.class);
	private char[] targetArr = null;
	private char[] sourceArr = null;
	private int[][] partionMatchTable = null;
	private static final int NOT_MATCH = -1;
	
	public static void main(String[] args) {
		String  target = "BBC ABCDAB ABCABCDABDDABCDABDE";
		String  match = "ABCDABD";
		
		KMPStringMatcher kmp = new KMPStringMatcher(target);
		System.out.println(kmp.find(match));
		
		
	}
 
	/**
	 * 构造器
	 * 
	 * @param targetStr
	 */
	public KMPStringMatcher(String targetStr) {
		if (targetStr == null)
			throw new NullPointerException("target string can not be null");
		this.targetArr = targetStr.toCharArray();
	}
 
	/**KMP算法匹配字符串的入口函数
	 * @param match
	 * @return
	 */
	public synchronized int find(String match) {
		if (match == null)
			throw new NullPointerException("match string can not be null");
 
		char[] matchArr = match.toCharArray();
		if (sourceArr == null || !isTwoCharArrEqual(sourceArr, matchArr)) {
			calculatePartionMatchTable(matchArr);
			sourceArr = matchArr;
		}
 
		if (targetArr.length < sourceArr.length)
			return NOT_MATCH;
 
		return getFirstPartionMatched(matchArr);
 
	}
 
	/**返回完全匹配的第一个字符位置
	 * @param matchArr
	 * @return
	 */
	private int getFirstPartionMatched(char[] matchArr) {
		int i = 0, j = 0, moveStep = 0;
		int firstPartion = NOT_MATCH;
		while (j < matchArr.length && i < targetArr.length) {
			if (matchArr[j++] != targetArr[i++]) {
				moveStep = (j == 1) ? 1 : (j - 1 - partionMatchTable[1][j - 2]); //后移位数
				i = i -j + moveStep;
				j = 0;
				continue;
			}
 
			if (j == matchArr.length) {
				firstPartion = i - j;
				break;
			}
		}
 
		return firstPartion;
 
	}
 
	/**计算部分匹配表：算法的关键
	 * 
	 * @param matcherString
	 * @return
	 */
	private boolean calculatePartionMatchTable(char[] match) {
		partionMatchTable = new int[2][match.length];
		partionMatchTable[0][0] = 0;
		partionMatchTable[0][1] = 0;
 
		int length = 0;
		char[] a, b;
		for (int i = 1; i < match.length; i++) {
			length = 0;
			for (int j = 0; j < i; j++) {
				a = getSubArr(match, 0, j);
				b = getSubArr(match, i - j, i);
				if (isTwoCharArrEqual(a, b))
					length = (a.length > length) ? a.length : length;
			}
 
			partionMatchTable[0][i] = i;
			partionMatchTable[1][i] = length;
		}
 
		return true;
	}
 
	/** 从一个字符数组中提取从 start 开始到 end 结束的子数组
	 * @param target
	 * @param start
	 * @param end
	 * @return
	 */
	public static char[] getSubArr(char[] target, int start, int end) {
		if (target == null || start < 0 || end >= target.length) {
			return null;
		}
 
		if (target == null || target.length == 0)
			throw new NullPointerException();
 
		char[] charArr = new char[end - start + 1];
		int count = start;
		int targetCount = start;
		while (count <= end)
			charArr[(count++) - start] = target[targetCount++];
 
		return charArr;
 
	}
	
	/** 判断两个字符数组是否equal ：基于数组元素判断
	 * @param from
	 * @param to
	 * @return
	 */
	public static boolean isTwoCharArrEqual(char[] from ,char[] to){
		if(from == null || to == null)
			return false ;
		
		if(from.length != to.length)
			return false ;
		
		int i = 0;
		int j = 0;
		int count =0;
		while(from[i++] == to[j++]){
			++count ;
			if(i >= from.length)
				break;
		}
		
		
		return (count == from.length)?true:false;
	
	}
	
	/**替换被匹配的目标文本
	 * @param replaceStr
	 * @return
	 */
	public synchronized boolean  replaceTheTargetStr(String replaceStr){
		if(replaceStr == null || replaceStr.equals(""))
			throw new NullPointerException();
		
		this.targetArr = replaceStr.toCharArray();
		
		return true ;
		
	}
 
}

————————-全文完——————————————————

KMP算法简介及代码实现

前提：

总结

如果你觉得受益欢迎赏杯咖啡，赞助点能量！感谢！

前提 ：

总结

如果你觉得受益欢迎赏杯咖啡，赞助点能量！感谢！

前提：