KMP算法

2023-12-18 05:45:49

KMP算法

应用场景-字符串匹配问题

  • 字符串匹配问题:
    • 有一个字符串 str1= ““硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好””,和一个子串 str2=“尚硅谷你尚硅你”
    • 现在要判断 str1 是否含有 str2, 如果存在,就返回第一次出现的位置, 如果没有,则返回-1

暴力匹配算法

  • 如果用暴力匹配的思路,并假设现在str1匹配到 i 位置,子串str2匹配到 j 位置,则有:
    • 如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符
    • 如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为0。
    • 用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。(不可行!)

KMP算法介绍

  1. KMP是一个解决模式串在文本串是否出现过,如果出现过,返回最早出现位置的经典算法。
  2. KMP算法利用之前判断过的信息,通过一个next数组,保存模式串中前后最长公共子序列的长度,每次回溯时,通过next数组找到,前面匹配过的位置,省去大量时间。

KMP算法详细介绍地址

代码实现

public class KMP {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = kmpNext("ABCDABD"); //[0,0,0,0,1,2,0]
        System.out.println("next="+ Arrays.toString(next));
        int index = kmpSearch(str1,str2,next);
        System.out.println("index= "+index);
    }
    /**
     * kmp搜索算法
     * @param str1 源串
     * @param str2 子串
     * @param next 部分匹配值
     * @return -1就是没匹配到,否则返回第一个匹配到的下标
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        //遍历
        for (int i = 0,j = 0; i < str1.length(); i++) {
            //需要处理 str1.charAt(i) != str2.charAt(j)去调整j的大小
            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;//如果字符串长度是1,部分匹配值就是0
        for (int i = 1,j=0; i < dest.length(); i++) {
            //当dest.charAt(i) != dest.charAt(j),我们需要从next[j-1]获取新的j
            //kmp算法核心
            while (j>0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }
            //当dest.charAt(i) == dest.charAt(j)时,部分匹配值+1
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

文章来源:https://blog.csdn.net/zzz479/article/details/135053385
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。