栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构(Java)KMP算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构(Java)KMP算法

一、应用场景-字符串匹配问题 1) 有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE ",和一个子串 str2="ABCDABD "  2) 现在要判断 str1 是否含有 str2 , 如果存在,就返回第一次出现的位置 , 如果没有,则返回 -1

 

二、解决方式-暴力匹配

        如果用暴力匹配的思路,并假设现在str1匹配到 i 位置,子串str2匹配到 j 位置,则有:

1) 如果当前字符匹配成功(即 str1[ i ] == str2[j] ),则 i ++ , j++ ,继续匹配下一个字符 2) 如果失配(即 str1[ i ]! = str2[j] ),令 i = i - (j - 1) , j = 0 。相当于每次匹配失败时, i 回溯 , j 被置为 0 。 3) 用暴力方法解决的话就会有大量的 回溯 ,每次只移动 一位 ,若是不匹配,移动到下一位接着判断,浪费了大量的时间。 ( 不可行 !)
  public static int violenceMatch(String source, String target) {
        int i = 0, j = 0;
        char[] s1 = source.toCharArray();
        char[] s2 = target.toCharArray();
        //任意一个索引越界了就结束 一般i越界了有可能没找到,j越界了是找到了
        while (i < source.length() && j < target.length()) {
            count++;
            //第一个字符匹配成功,接着往下面匹配
            if (s1[i] == s2[j]) {
                i++;
                j++;
            } else {
                //匹配不成功,从下一个位置重新开始匹配
                i = i - j + 1;
                j = 0;
            }
            //j指向了目标字符串的最后,匹配成功了
            if (j == target.length()) return i - j;
        }
        return -1;
    }
三、解决方式-KMP算法 1) KMP 是一个解决模式串在文本串是否出现过,如果出现过,最早出现的位置的经典算法 2) Knuth-Morris-Pratt 字符串查找算法 ,简称为 “ KMP 算法”,常用于在一个文本串 S 内查找一个模式串 P 的出现位置,这个算法由 Donald Knuth 、 Vaughan Pratt 、 James H. Morris 三人于 1977 年联合发表,故取这 3 人的姓氏命名此算法 . 3) KMP 方法算法就利用之前判断过的信息,通过 一个next数组 ,保存模式串中前后 最长公共子序列 的 长度 ,每次回溯时,通过 next 数组找到,前面匹配过的位置,省去了大量的计算时间。         其实kmp算法与暴力算法的区别在于暴力算法每次匹配只后移一位,而kmp算法利用next数组动态地计算每次匹配后移的位数。next数组利用目标字符串在匹配前就已得出。

   

3.1 前缀与后缀

3.2 next数组与部分匹配值: 

 3.3 举例

假如我们已经匹配到了这里,可以看到下一个字符不匹配。

 

如果按照暴力方法,下一次匹配的位置应该是最开始匹配位置的后一位:

 

利用KMP算法,计算出下一次后移的位数是 4 位:

(已匹配字符数(6)- 最后一个已匹配字符的部分匹配值(2))

 四、KMP的代码演示

1、首先是获取next数组,这个是网上的版本,我不理解。我在主程序中用别的思路实现了同样的结果

 //获取next数组的网上版本,我看不懂
    public static int[] Next1(String s) {
        int[] next = new int[s.length()];
        next[0] = 0;//第一个元素无论如何都是0,不跟自己匹配
        //索引后移
        for (int i = 1, k = 0; i < s.length(); i++) {
            while (k > 0 && s.charAt(k) != s.charAt(i)) k = next[k - 1];//
            if (s.charAt(k) == s.charAt(i)) k++;//如果某次匹配到了,就让匹配长度+1
            next[i] = k;//不论每次是否匹配到都把k赋给next的对应元素,也就是匹配长度
        }
        return next;
    }

2.主程序

注:next数组的思路:

      1.  i指向字符串首位,j指向字符串首位的后一位。j 不断后移,直到遇到和首位相同的字符时 i、j同时后移,这时同时记录匹配长度到next数组中。

      2. 一旦又遇到了不同的字符,i 就回到字符串首位,而 j 始终后移。清空 匹配长度变量,等待下一次匹配。

      3.如果又匹配成功了,就重复类似于 1 的操作(i、j同时后移)。直到 j 指到了字符串末尾。

public static Integer count=0;//匹配次数计数,对比两种方法
public static int KMPMatch(String source,String target){
         //1、获得next数组,这是kmp算法的关键,这样我们才能决定下次从哪里开始匹配
         int[] next = new int[target.length()];
         int matchedLength = 0, i = 0, j = 1;
         next[0] = 0;//第一个元素无论如何都是0,不跟自己匹配
         //i指向字符首位,j后移。
         while (j < target.length()) {
             //如果 i 与 j 所指字符匹配成功,就同时后移,同时记录匹配的字符长度
             if (target.charAt(i) == target.charAt(j)) {
                 next[j] = ++matchedLength;
                 i++;
                 //否则就把 i 移到首位,匹配长度清零
             } else {
                 i = 0;
                 matchedLength = 0;
             }
             //j始终向后遍历
             j++;
         }
         //2、真正的匹配过程
         int k = 0, l = 0;//k指向源字符串,l指向目标字符串
         int matched=0;
         char[] s1 = source.toCharArray();
         char[] s2 = target.toCharArray();
         //任意一个索引越界了就结束 一般i越界了有可能没找到,j越界了是找到了
         while (k < source.length() && l < target.length()) {
             count++;
             //第一个字符匹配成功,接着往下面匹配
             if (s1[k] == s2[l]) {
                 k++;
                 l++;
                 matched++;

             } else {
                 //匹配不成功,从后面位置重新开始匹配,这个位置经过了kmp算法的优化
                 if(matched>=1) k=k-l+matched-next[matched-1];//字符长度不为0,那就根据算法选择下次开始比较的位置
                 else k=k-l+1;//字符长度为0,那就跟暴力方法一样回到原来位置的下一位
                 l = 0;
                 matched=0;
             }
             //l指向了目标字符串的最后,匹配成功了
             if (l == target.length()) return k - l;
         }
         return -1;
     }
五、最终对比
@Test
    public void testViolenceMatch() {
        String source = "BBC ABCDAB ABCDABCDABDE";
        String target = "ABCDABD";
        System.out.println(solution.violenceMatch(source, target));
        System.out.println("匹配次数:"+solution.count);
    }



15
匹配次数:36



    @Test
    public void testKMPMatch() {
        String source = "BBC ABCDAB ABCDABCDABDE";
        String target = "ABCDABD";
        System.out.println(solution.KMPMatch(source,target));
        System.out.println("匹配次数:"+solution.count);
    }



15
匹配次数:29

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950895.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号