Java实现KMP算法的字符串匹配

74 阅读 0 评论 49 点赞

我是靠谱客的博主懵懂热狗，最近开发中收集的这篇文章主要介绍Java实现KMP算法的字符串匹配，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

KMP算法往往是和朴素模式匹配算法相对比的，后者是一种暴力解决算法，用模式串与主串的每个子串一一比较。最终确定模式串在主串的起始位置。

主串：dfaabaafh3
模式串：aabaa

肉眼可以看出模式串是在主串第3个字符开始出现的。如果使用朴素模式匹配算法，则一共有(n-m)+1个子串，n是主串长度，m是模式串长度。所以说需要比较(n-m)+1次。每次又需要比较m次，所以最坏的情况下，整个朴素模式匹配的算法时间复杂度是o(mn)。

KMP算法的时间复杂度可以控制在 o(m+n），核心就是kmp算法可以让主串的指针不回溯，主串的指针一直向前移动，而动态的变化模式串的指针。而动态变化模式串指针的关键就是，当遇到某一个不匹配字符时，需要找到模式串当前这个字符之前的子串的最长相等前后缀。求出最长相等前后缀的长度，最终求出当前字符的下个指针应该是 (字串长度) - （字串长度 - （模式串匹配的长度）） + 1。求某个字符前面字符的公共前后缀的长度，定义两个指针，主串指针不断移动，如果与模式串不匹配，则模式串指针重置为1。

求next数组代码实现如下


//获取某个模式串的next数组（整个过程就是找模式串的不匹配字符之前的字串的最长相等前后缀，找到以后将前缀
// 移动到后缀位置，模式串指针此时等于（字串长度） - （字串长度 - 最长相等前后缀长度） + 1 ）
private static int[] getNextArr(char[] chars) {
int[] next = new int[chars.length];//存储每个字符的next指针，也是从1开始存储
next[1] = 0;//如果第一次字符就不匹配了，则主串指针和模式串指针都需要++,但是需要先将模式串指针修改为0，再++
next[2] = 1;//如果遇到第二个字符不匹配了，则从第一个字符开始
//从第三个字符开始求字串的最长相等前后缀（注意,最长相等前后缀的长度不能等于子串的长度）
int i = 3;
while (i < chars.length) {
//定义两个指针，一个指向模式串，另一个指向模式串复制出来的主串
int modelIndex = 1;//从第一个字符开始扫描
int mainIndex = 2;//从第一个字符开始扫描
//主串的指针不能超过当前字串的长度（这里应该用主串的指针，因为模式串的指针是可能被重置为1的）
while (mainIndex < i) {
//模式串modelIndex与主串mainIndex指进行比较，如果相等，同时++
char mainChar = chars[mainIndex];
char modelChar = chars[modelIndex];
if (mainChar == modelChar) {
modelIndex++;
mainIndex++;
} else {
//只让mainIndex++
mainIndex++;
modelIndex = 1;
}
}
//循环结束后，modelIndex--,算出实际的相等前缀长度
modelIndex--;
int nextIndex = (i - 1) - ((i - 1) - modelIndex) + 1;
next[i] = nextIndex;
i++;
}
return next;
}

求模式串的位置实现代码如下


//获取模式串在主串中的位置，如果没有，则返回0（从下标1开始存元素的）
private static int indexOf(char[] mainChar, char[] modelChar, int[] next) {
//KMP算法的核心就是使得主串的指针不会回溯
int mainCharIndex = 1;//主串的指针
int modelCharIndex = 1;//模式串的指针
//while循环条件
while (mainCharIndex < mainChar.length ) {
char mainc = mainChar[mainCharIndex];
char modelc = modelChar[modelCharIndex];
if (mainc == modelc) {
//主串和模式串相等，继续比较
mainCharIndex++;
modelCharIndex++;
if (modelCharIndex >= modelChar.length) {
//说明模式串已经比较完了
break;
}
} else {
//如果不一致，则需要找到模式串当前不匹配字符的next下标
int nextIndex = next[modelCharIndex];
modelCharIndex = nextIndex;//让模式串从nextIndex开始与主串当前位置进行比较
if (modelCharIndex == 0) {
//如果模式串返回0，则表示第一个主串与模式串的第一个字符就不匹配，则此时需要同时++
modelCharIndex++;
mainCharIndex++;
}
}
}
if (modelCharIndex >= modelChar.length) {
//模式串指针已经全部走完了,可以匹配
return mainCharIndex - ( modelChar.length - 1) ; //主串指针减去模式串长度
} else {
return 0;
}
}

这里注意，当遇到不匹配字符时，要获取这个字符处的next指针，如果指针是0，则应该让主串指针和模式串指针同时++。

测试代码如下


public static void main(String[] args) {
char[] chars = {'', 'a', 'a', 'b', 'a', 'a', 'f'};//0处位置废弃不存储任何元素，从1开始存元素
int[] next = getNextArr(chars);
for (int i = 1; i < next.length; i++) {
System.out.println("字符" + i + "的next
==> " + next[i]);
}
//匹配主串
char[] mainChar = {'', 'd', 'f', 'a', 'a', 'b','a', 'a', 'f', 'h', '3'};
int position = indexOf(mainChar, chars, next);
System.out.println("position = " + position);
}

next数组问题

next数组的前两个下标值都是固定的，-1，0或者是0，1，如果是-1，0，则表示模式串指针从0开始，如果是0，1，则表示模式串指针从1开始，那么当从0开始时，如果next[j]=-1，则表示此时主串指针和模式串指针都需要++，同理，如果时从1开始，如果next[j]=1，则表示主串指针与模式串指针都需要++。
最长公共前后缀问题：这里注意，前缀不包含最后一个字符，后缀不包含第一个字符，且前缀与后缀的顺序都是从左往右，后缀也不是从右往左。
设主串长度为n，模式串长度为m，如果是朴素模式匹配算法，则在最坏情况下，需要长度为n的主串含有长度为m的模式（n-m+1）个，每次需要比较m次，则朴素模式算法的时间复杂度为o(mn)。省略了mm+m，因为与长度为n的主串相比，模式串长度往往远远小于主串。那么对于KMP算法来说，时间复杂度主要分为，求next数组以及匹配，求next数组只和模式串长度m有关，o(m)，由于主串指针不需要回溯，那么主串匹配的时间复杂度为o(n),则整个时间复杂度为o(m+n)。