Java实现KMP代码

ゝ一世哀愁。 2022-09-10 00:13 154阅读 0赞

左神第12节课：  
基础提升：有序表、并查集

## BM算法： ##

实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n\*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。

https://zh.wikipedia.org/wiki/KISS%E5%8E%9F%E5%88%99

KMP算法是由一个问题而引发的：

> 对于一个字符串str（长度为N）和另一个字符串match（长度为M），如果match是str的子串，请返回其在str第一次出现时的首字母下标，若match不是str的子串则返回-1。

public class KMP {
        
        public static void main(String[] args) {
        
            System.out.println(getIndexOf("abcacb", "cb"));
        }
    
    
        public static int getIndexOf(String str, String m) {
        
            if (str == null || m == null || m.length() < 1 || str.length() < m.length())
                return -1;
    
            char[] chs1 = str.toCharArray();
            char[] chs2 = m.toCharArray();
            if (chs1.length < chs2.length) return -1;
            int[] next = getNextArr(chs2);
    
            int i1 = 0, i2 = 0;
    
            while (i1 < str.length() && i2 < m.length()) {
        
                //正常匹配的就一个一个向着后面走
                if (chs1[i1] == chs2[i2]) {
        
                    i1++;
                    i2++;
                    //如果当前的指针指向最后一个的时候，说明i1当前位置与i2所有可能的快速方法都不匹配
                } else if (next[i2] == -1) {
        
                    i1++;
                    //当前不ok，那么尝试去看看下一个next数组总的结点但是否可行
                } else {
        
                    i2 = next[i2];
                }
                System.out.println(1);
            }
    
            return i2 == m.length() ? i1 - i2 : -1;
        }
    
        public static int[] getNextArr(char[] ms) {
        
            if (ms.length == 1) return new int[]{
        -1};
            int[] next = new int[ms.length];
            next[0] = -1;
            next[1] = 0;
            int i = 2;
            int cn = 0;
            // 保证i没有越界
            while (i < ms.length) {
        
    //            i位置的都基于前面的数据
                if (ms[i - 1] == ms[cn]) {
        
                    next[i++] = ++cn;
    //          只有cn > 0的时候才能够继续向着前面不停遍历
                } else if (cn > 0) {
        
                    cn = next[cn];
    //            遍历到cn也等于0了，没办法了，就直接将这个点的数据设置为0
                } else {
        
                    next[i++] = 0;
                }
            }
            return next;
        }
    }