欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

KMP字符串匹配算法

程序员文章站 2022-06-28 08:21:08
KMP字符串匹配算法...

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;
	}
}

总结

理解上有点难度。

本文地址:https://blog.csdn.net/qq_37665301/article/details/110198745