KMP字符串匹配算法_Java

KMP字符串匹配算法

- - 代码
  - 总结

代码

import java.util.Arrays;

/**
 * kmp字符串匹配算法
 * 知识点：前缀、后缀、部分匹配表
 * @author dxt
 *
 */
public class KMPAlgorithm {
	public static void main(String[] args) {
		//1. 获取 查找字符串集 和 目标字符串
		String str1 = "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDA";
		//2. 获取目标串的部分匹配表
		int[] next = getKMPTable(str2);
		System.out.println(Arrays.toString(next));
		//3. 进行kmp搜索查找
		int result = KMPSearch(str1, str2, next);
		System.out.println(result);
	}
	
	/**
	 * 在str1中查找str2，如果找到返回初始字母索引值，否则返回-1；next是str2的部分匹配表
	 * @param str1
	 * @param str2
	 * @param next
	 * @return
	 */
	public static int KMPSearch(String str1, String str2, int[] next) {
		//从str1字符串头开始进行kmp匹配
		for(int i=0, j=0; i<str1.length(); i++) {
			//对应字符不相等，j变小，相当于向右移str2
			while(j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = next[j-1];
			}
			//对应字符相等，比较下一个字符
			if(str1.charAt(i) == str2.charAt(j)) {
				j++;
			}
			//最后一个字符比完，说明存在子串，返回第一个字符的索引
			if(j == str2.length()) {
				return i-j+1;
			}
		}
		return -1;
	}
	
	/**
	 * 整个方法的作用时 获取字符串str的部分匹配表， 与 原字符串匹配无关
	 * 步骤：（1）前后缀不相同
	 * 	   （2）前后缀相同
	 *     （3）为table[i]赋值
	 * @param str
	 * @return
	 */
	public static int[] getKMPTable(String str) {
		int[] table = new int[str.length()];
		table[0] = 0;	
		//i:后缀末尾 j:前缀末尾；j还表示i之前（包括i）最长相等前后缀的长度
		for(int i=1, j=0; i<str.length(); i++) {
			//当str.charAt(i) != str.charAt(j), 需要从table[j-1]获取新的j
			while(j > 0 && str.charAt(i) != str.charAt(j)) {
				j = table[j-1];	//j向前回退， 此时j的含义为 前缀末尾
			}
			
			//当 str.charAt(i) == str.charAt(j) 满足时，部分匹配值+1
			if(str.charAt(i) == str.charAt(j)) {
				j++;
			}
			
			//赋值
			table[i] = j;
		}
		return table;
	}
}