暴力匹配字符串的升级版算法 —— Kmp算法

本文主要是介绍暴力匹配字符串的升级版算法 —— Kmp算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

一、Kmp算法是什么？

简单来说，KMP（Knuth-Morris-Pratt）算法主要用于解决字符串匹配问题。也就是当你有一个主串（text）和一个模式串（pattern）时，KMP算法可以在主串中快速找到模式串的出现位置。其核心思想是利用已经部分匹配的信息来避免不必要的匹配尝试。
相对于我们最开始使用的暴力匹配两个字符串是否相等的时间复杂度大大降低。、
上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！

二、算法分析

1.构建next数组

KMP需要next数组的辅助，那么它是如何来生成的呢？可以采用递推的方式进行快速求解，利用已经掌握的信息来避免重复的运算。
其中next数组是使用匹配串进行构建出来的，它通过使用一个preCommonLen的变量来记录这个字符串的共同公共前缀。


根据上面得出，这个next就是记录了存放这个数组前后具有相同的前后缀

在生成呢next[ ]的过程中，如果遇到不一样的字符该怎么办呢？

​ 其实可以找出不一样的字符的前一位，例如上面的 C与B不相同，那么就找最近的A重新比较，也就是左边字符串的后缀A

因为这里A的下标为 1 ，跳过一位，那么就是从B开始判断； 则右边的从B开始进行重新比较

所以蓝色箭头的值与黄色箭头的值一样，所以重新有共同的字串，则黄色箭头的值为 2

就这样我们就完成了Kmp算法的核心：构建next[ ]数组

 // todo 构建next数组private static int[] buildedString(String patternString/*匹配串，不是主串*/,int[] arrayPatternNext) {int prefix_len=0;// 共同前缀int i=1;//从下标1开始，因为第0位前缀为0char[] chars=patternString.toCharArray();while (i<patternString.length()){if (chars[prefix_len]==chars[i]){prefix_len+=1;arrayPatternNext[i]=prefix_len;i+=1;}else {if (prefix_len==0){//没有公共前缀arrayPatternNext[i]=0;i+=1;}else prefix_len=arrayPatternNext[prefix_len-1];// 不相等且有公共前缀，那么需要根据next数组来更新公共前缀}}return arrayPatternNext;}

---

2.匹配主串

步骤：

1 i 下标是不会回溯的，只会往前；

2 如果两个字符串的相同下标的比较字符相等的话，就进行向下移动；

3 当匹配中有不一样的字符时，就会去找next【】数组的相同子串后缀下标的值，并进行跳过多少位。

例如这里跳过了 2 位，所以子串下标 j = 2 ，指在了【0,1,2】第三号元素进行下一次的重新匹配，完美的跳过了上一次的重复字符，避免了回溯带来的时间损耗，这个就是KMP算法的魅力了。

// 字符串的匹配private static int getCommonString(String a/*主串*/, String patternString, int[] arrayPatternNext) {int i=0;int j=0;while (i<a.length()){// 主串的下标一直往前走，则时间复杂度为线性if (a.charAt(i)==patternString.charAt(j)){i+=1;j+=1;}else if (j>0){//因为当前面不匹配的时候，这个匹配串的下标就需要根据next数组作出调整j=arrayPatternNext[j-1];}else i+=1; //不相等，字串下标也没有动，主串下标就往前走if (j==patternString.length()-1){ //模式串的j到达了末尾commonLen=i-j+1;// 直接计算长度并返回break;}}return commonLen;}

三、完整代码

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;public class Kmp {static  int commonLen=0;public static void main(String[] args) throws IOException {BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));System.out.println("输入主串：");String a=bufferedReader.readLine();System.out.println("输入匹配串");String patternString=bufferedReader.readLine();if (a.length()<patternString.length()) System.out.println("主串需要大于等于匹配串");else {int[] arrayPatternNext=new int[patternString.length()];Arrays.fill(arrayPatternNext,0);arrayPatternNext=buildedString(patternString,arrayPatternNext);System.out.println(getCommonString(a,patternString,arrayPatternNext)==0?"主串没有找到匹配串":"主串存在该匹配字串");}}private static int getCommonString(String a, String patternString, int[] arrayPatternNext) {int i=0;int j=0;while (i<a.length()){// 主串的下标一直往前走，则时间复杂度为线性if (a.charAt(i)==patternString.charAt(j)){i+=1;j+=1;}else if (j>0){//因为当前面不匹配的时候，这个匹配串的下标就需要根据next数组作出调整j=arrayPatternNext[j-1];}else i+=1; //不相等，字串下标也没有动，主串下标就往前走if (j==patternString.length()-1){commonLen=i-j+1;break;}}return commonLen;}// todo 构建next数组private static int[] buildedString(String patternString,int[] arrayPatternNext) {int prefix_len=0;// 共同前缀int i=1;char[] chars=patternString.toCharArray();while (i<patternString.length()){if (chars[prefix_len]==chars[i]){prefix_len+=1;arrayPatternNext[i]=prefix_len;i+=1;}else {if (prefix_len==0){//没有公共前缀arrayPatternNext[i]=0;i+=1;}else prefix_len=arrayPatternNext[prefix_len-1];}}return arrayPatternNext;}
}

这篇关于暴力匹配字符串的升级版算法 —— Kmp算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---