KMP字符串匹配算法
程序员文章站
2022-06-28 08:21:08
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
上一篇: 新站标题搜索不到 没有任何排名是降权了么 详细解答
下一篇: 面试 | 软通动力技术面