罕用十大算法（四）— KMP算法

<!-- more -->

博客阐明

文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！

介绍

KMP是一个解决模式串在文本串是否呈现过，如果呈现过，最早呈现的地位的经典算法

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，罕用于在一个文本串S内查找一个模式串P 的呈现地位，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联结发表，故取这3人的姓氏命名此算法.

KMP办法算法就利用之前判断过信息，通过一个next数组，保留模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，后面匹配过的地位，省去了大量的计算工夫

字符串匹配问题

  • 有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"
  • 当初要判断 str1 是否含有 str2, 如果存在，就返回第一次呈现的地位, 如果没有，则返回-1
  • 要求：应用KMP算法实现判断，不能应用简略的暴力匹配算法
暴力匹配算法

如果以后字符匹配胜利（即str1[i] == str2[j]），则i++，j++，持续匹配下一个字符

如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

代码实现
package com.guizimo;public class ViolenceMatch {    public static void main(String[] args) {        String str1 = "BBC ABCDAB ABCDABCDABDE";        String str2 = "ABCDABD";        int index = violenceMatch(str1, str2);        System.out.println("index=" + index);    }    public static int violenceMatch(String str1, String str2) {        char[] s1 = str1.toCharArray();        char[] s2 = str2.toCharArray();        int s1Len = s1.length;        int s2Len = s2.length;        int i = 0;        int j = 0;        while (i < s1Len && j < s2Len) {            if(s1[i] == s2[j]) {                i++;                j++;            } else {                i = i - (j - 1);                j = 0;            }        }        if(j == s2Len) {            return i - j;        } else {            return -1;        }    }}
KMP算法
  • 失去子串的局部匹配表
  • 应用局部匹配表实现KMP匹配
代码实现
package com.guizimo;import java.util.Arrays;public class KMPAlgorithm {    public static void main(String[] args) {        String str1 = "BBC ABCDAB ABCDABCDABDE";        String str2 = "ABCDABD";                int[] next = kmpNext("ABCDABD");         System.out.println("next=" + Arrays.toString(next));                int index = kmpSearch(str1, str2, next);        System.out.println("index=" + index);     }        //KMP搜寻    public static int kmpSearch(String str1, String str2, int[] next) {        for(int i = 0, j = 0; i < str1.length(); i++) {            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;    }    //获取局部匹配表    public static  int[] kmpNext(String dest) {        int[] next = new int[dest.length()];        next[0] = 0;        for(int i = 1, j = 0; i < dest.length(); i++) {            while(j > 0 && dest.charAt(i) != dest.charAt(j)) {                j = next[j-1];            }            if(dest.charAt(i) == dest.charAt(j)) {                j++;            }            next[i] = j;        }        return next;    }}

感激

尚硅谷

以及勤奋的本人，集体博客，GitHub