经典算法KMP

分手后的思念是犯贱 2022-05-26 04:22 152阅读 0赞

![这里写图片描述][70]

//KMP算法
    public class KMPTest{
    
        //方法:获得模式串在母串的位置
        public static int getIndexOf(String s,String m){
            if(s==null||m==null||m.length()<1||s.length()<m.length()){
                return -1;
            }
            char[]ss=s.toCharArray();  //主串字符串转数组
            char[]ms=m.toCharArray();  //子串字符串转数组
            int si=0;
            int mi=0;
            int[]next=getNextArray(ms);
            while(si<ss.length&&mi<ms.length){
                if(ss[si]==ms[mi]){
                    si++;
                    mi++;
                }else if(next[mi]==-1){
                    si++;
                }else{
                    mi=next[mi];
                }
            }
            return mi==ms.length?si-mi:-1;
    
        }
        //获得模式串的next数组
        public static int[]getNextArray(char[]ms){
           if(ms.length==1){
              return new int[]{-1};
           }
           int[]next=new int[ms.length];
           next[0]=-1;
           next[1]=0;
           int pos=2;
           int cn=0;
           while(pos<ms.length){
                if(ms[pos-1]==ms[cn]){
                    next[pos++]=++cn;
                }else if(cn>0){
                     cn=next[cn];
                }else{
                    next[pos++]=0;
                }
           }
           return next;
        }
        public static void main(String[]args){
            //System.out.println("Hello");
             String s="abcdefgh";
             String m="fgh";
    
             String s1="abcdefgh";
             String m1="fgx";
    
             System.out.println(getIndexOf(s,m));
             System.out.println(getIndexOf(s1,m1));
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220526/d463a150ddc849f0be7113f0b99701fd.png
[70 1]: /images/20220526/c976066dcfaa4b40b740d23376207356.png

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法JavaScript(五) ：串(经典KMP算法)

KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法，看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同前缀匹配是指：模式串和母串的比较从左到右，模式串的

你的名字/ 2022年08月06日 13:28/ 0 赞/ 194 阅读

相关 KMP算法

1.原始的字符串匹配方法算法基本思想：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较

「爱情、让人受尽委屈。」/ 2022年06月15日 01:42/ 0 赞/ 189 阅读

相关 KMP 算法

个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next\[i\]确实有很多版本啊

小鱼儿/ 2022年06月08日 03:25/ 0 赞/ 154 阅读

相关【算法】KMP算法

【[fishing-pan][]：[https://blog.csdn.net/u013921430][https_blog.csdn.net_u013921430]转载请注

淩亂°似流年/ 2022年05月30日 04:27/ 0 赞/ 387 阅读

相关经典的KMP算法

![20180326193937367][] ![20180326152615893][] //KMP算法(手写大名鼎鼎的kmp)经典的KMP算法时间复杂度为

「爱情、让人受尽委屈。」/ 2022年05月28日 00:21/ 0 赞/ 147 阅读

相关算法 kmp算法

kmp算法是改进后的字符匹配算法，它与bf算法的区别是，每次从串与主串匹配失败后，从串与主串匹配的位置不同。下面具体说下这两种算法的区别：主串：BABCDABABCDA

客官°小女子只卖身不卖艺/ 2022年05月26日 04:40/ 0 赞/ 250 阅读

相关经典算法KMP

![这里写图片描述][70] //KMP算法 public class KMPTest{ //方法:获得模式串在母串的位置

分手后的思念是犯贱/ 2022年05月26日 04:22/ 0 赞/ 153 阅读

相关ＫＭＰ算法

核心：１.当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将搜索串往后多滑动几位　　　２．构建《部分匹配表》下面链接是阮大神的见解，写的非常棒！　　　[字符串

谁践踏了优雅/ 2022年03月02日 06:26/ 0 赞/ 282 阅读

相关 Kmp算法

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ ![bg2013050101.jpg][]

迷南。/ 2021年12月17日 11:13/ 0 赞/ 342 阅读

相关 KMP算法

一 KMP算法介绍 1 KMP是一个解决模式串在文本串是否出现过，如果出现过，求算出现的位置的经典算法。 2 Knuth-Morris-Pratt 字符串查找算法，简称

傷城~/ 2021年07月24日 18:29/ 0 赞/ 587 阅读