KMP算法详解

KMP算法详解

说明

1. KMP算法是一种字符串查找算法，能较高效的从一个长字符串中匹配到模式串，即子串
2. KMP算法是暴力匹配算法的升级版，主要优化了暴力匹配在每次回溯时从当前匹配字符的下一个字符开始匹配的问题，因为有些字符已经匹配过
3. KMP核心思想为改变每次匹配失败回溯时的下一个字符位置问题，即不是从当前匹配失败的下一个字符开始继续匹配，而是跳过已经匹配过的字符，从未匹配过的字符开始继续匹配
4. 基于部分匹配表来实现，部分匹配表是前缀和后缀最长共有子串的长度形成的一维数组
5. 通过部分匹配表查找和当前元素相同的下一元素的位置，即记录两相同元素的间隔值，下次回溯时指针直接向右移动间隔值大小的位置
6. 源码见下

源码及分析

package algorithm.algorithm.kmp;

import java.util.Arrays;

/**
 * @author AIMX_INFO
 * @version 1.0
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = kmpNext(str2);
        System.out.println(Arrays.toString(next));
        int index = KMPSearch(str1, str2, next);
        System.out.println("index = " + index);

    }
    //实现KMP搜索算法
    /**
     *
     * @param str1 原始字符串
     * @param str2 子串
     * @param next 部分匹配表
     * @return 返回搜索的结果
     */
    public static int KMPSearch(String str1, String str2, int[] next){
        //遍历初始字符串插找子串
        for (int i = 0, j = 0; i < str1.length(); i++) {
            //匹配某几位后如果后一位不再匹配，则重置 j
            while (j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j - 1];
            }
            //判断当前长串的某一位是否匹配子串，如果匹配，继续判断下一位
            if (str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            //对比结束后，如果子串的长度等于 j的大小，则说明匹配成功
            if (j == str2.length()){
                return i - j + 1;
            }
        }
        return -1;
    }

    //编写方法实现子串的部分匹配表
    /**
     * @param str 要获取的部分匹配表的子串
     * @return 返回部分匹配表
     */
    public static int[] kmpNext(String str) {
        //创建数组模拟部分匹配表
        int[] next = new int[str.length()];
        //单个字符的匹配值始终为0
        next[0] = 0;
        //i为遍历这个子串的索引， j为遍历到的字符和前边重复字符串的长度
        for (int i = 1, j = 0; i < str.length(); i++) {
            //如果有重复子串，当下一位不重复后，重置 j
            while (j > 0 && str.charAt(i) != str.charAt(j)){
                j = next[j - 1];
            }
            //如果遍历到的字符和前边的字符重复，则j++,判断下一位是否重复
            if (str.charAt(i) == str.charAt(j)){
                j++;
            }
            //将重复的值存储到部分匹配表
            next[i] = j;
        }
        return next;
    }
}

KMP算法详解

原文：https://www.cnblogs.com/mx-info/p/14888146.html