KMP算法

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;
    }
}