kmp以及算法中如何使用kmp去解决问题

ゞ浴缸里的玫瑰 2023-02-15 03:46 5阅读 0赞

## 一、看一个问题 ##

两个字符串abcabcdeanc和abcd，我们判断后面的字符串是否时前面字符串的子串，如果是返回数组下标，否则返回-1。

### 暴力解法 ###

public static int matchStr(String s,String m){
            if(s == null || m ==  null || s.length() < 1 || s.length() < m.length()){
                return -1;
            }
            char[] str1 = s.toCharArray();
            char[] str2 = m.toCharArray();
            int sindex = 0;
            int mindex = 0;
            while(sindex < str1.length && mindex < str2.length){
                if(str1[sindex] == str2[mindex]){
                    sindex++;
                    mindex++;
                }else{
                    sindex = sindex - mindex + 1;
                    mindex = 0;
                }
            }
            return mindex == str2.length ? sindex - mindex : -1;
        }

不多解释了这个算法，时间复杂度O(m \* n)。

### KMP算法 ###

对于暴力解法，在匹配失败后回退一直是挨个字符遍历，没有用到字符串的特性。而kmp利用next数组解决了这一点。

看图（要匹配的字符串str2）：

![20200604145034345.png][]

如果当前i = 6指向最后一个字符，那么next\[i\]表示的就是前0 - i-1字符的最大前缀和后缀长度（前缀和后缀相同）。

前缀：

![20200604145316813.png][]

后缀：

![20200604145337750.png][]

同时呢，计算这个前缀后足长度的时候，这个长度不允许等于i，也就是前缀和后缀不能是整个前面的字符串（如果没有这个要求，那么前缀和后缀都必然是前面字串）。

那么如何机算next\[\]呢？初始状态next\[0\] = -1，next\[1\] = 0，很好理解，下标0之前的东西根本没有，下标1之前只有一个字符，但是这个字符不允许用，那么就是0。我们来看建立的过程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

设置一个变量cn，这个很重要，表示最长前缀（前缀和后缀相等）的长度，同时也是前缀的下一个位置，起初i=2。

比如 i = 5，ab是最长前缀那么cn就是红色箭头所指，cn = 2：

![20200604152154951.png][]

分为下面几种情况：

（1）如果chars\[cn\] == chars\[i - 1\]，那么直接next\[i\] = ++cn；i++

（2）如果不等于，同时cn大于0，也就是说不是指向第一个位置，那么cn = next\[cn\]，相当于拿到了cn之前字符串的最长前缀和后缀的位置的下一个位置。

（3）如果cn == 0，那么直接赋值0。i++。

目前：i = 2，cn = 0。判断i- 1位置和cn位置字符是否相同，不相同。则next\[i\] = 0。

一直到i = 4。next\[i\] = 1，表示前面abca的最大前缀和后缀相同的长度是1.这个时候cn = 1，表示要比较下一个字符。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

i = 5的时候i - 1和cn = 1的字符相同，那么cn++，同时next\[i\] = 2。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2][]

最后数组如图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3][]

上面过程没有出现情况2，对于情况2，cn = next\[cn\]，以前面最长前缀为字符串，找到这个字符串的最长前缀位置，然后再比较。

public static int[] getNextArr(char[] chars){
            if(chars.length < 2){
                return new int[]{-1};
            }
            int[] next = new int[chars.length];
            next[0] = -1;
            next[1] = 0;
            int i = 2;
            //跳到的位置
            int cn = 0;
            while(i < next.length){
                if(chars[i - 1] == chars[cn]){
                    next[i++] = ++cn;
                }else if(cn > 0){
                    //如果不相等，跳转前一个最长前缀
                    cn = next[cn];
                }else{
                    //到了第一个字符串
                    next[i++] = 0;
                }
            }
            return next;
        }

之后明确了这个数组，我们来看一下kmp

public static int getIndexOf(String s,String m){
            if(s == null || m ==  null || s.length() < 1 || s.length() < m.length()){
                return -1;
            }
            char[] str1 = s.toCharArray();
            char[] str2 = m.toCharArray();
            int sindex = 0;
            int mindex = 0;
            int[] next = getNextArr(str2);
            while(sindex < str1.length && mindex < str2.length){
                if(str1[sindex] == str2[mindex]){
                    sindex++;
                    mindex++;
                }else if(next[mindex] == -1){
                    sindex++;
                }else{
                    mindex = next[mindex];
                }
            }
            return mindex == str2.length ? sindex - mindex : -1;
        }

先看主体思路，s字符串是不回退的，只通过next改变m字符串的下标。这里分为三种情况：

（1）如果发现相等，同时数组下标移动。

（2）如果发现m字符串第一个字符与s字符串不相同，那么s字符串下标移动。

（3）如果发现不匹配并且不是第一个字符，那么m字符串回退。如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4][]

然后开始匹配！！！发现不同

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5][]

之前暴力方法的移动是这样的：

![20200604154821196.png][]

kmp：通过查找next数组。next\[6\] = 3，那么mindex = 3。然后再比较。

![20200604155016256.png][]

最后直到查找完毕。

## 二、kmp算法的应用 ##

### 1、京东笔试题 ###

题目：首先有一个原始串，例如str = "abcabc"，要搞成一个新的字符串（其中饱汉两个原始串），新的字符串="abcabcabc"，要求长度最短。

我们可以这样搞！我们找出这个字符串"abcabc"的最长前缀len，也就是abc，然后令i = len 遍历到结束，添加字符。

public static int getNextArr(char[] chars){
            if(chars.length < 2){
                return -1;
            }
            int[] next = new int[chars.length + 1];
            next[0] = -1;
            next[1] = 0;
            int i = 2;
            //跳到的位置
            int cn = 0;
            while(i < next.length){
                if(chars[i - 1] == chars[cn]){
                    next[i++] = ++cn;
                }else if(cn > 0){
                    //如果不是第一个
                    cn = next[cn];
                }else{
                    //到了第一个字符串
                    next[i++] = 0;
                }
            }
            return next[next.length - 1];
        }
    
        public static void main(String[] args) {
            String string = "abcabca";
            char[] arr = string.toCharArray();
            int len = getNextArr(string.toCharArray());
            System.out.println(len);
            StringBuffer buffer = new StringBuffer();
            buffer.append(string);
            for(int i = len ;i < arr.length;i++){
                buffer.append(arr[i]);
            }
            System.out.println(buffer.toString());
        }

### 2、判断一棵树中是否包含一棵子树 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6][]

首先对左边二叉树进行序列化用\#表示null，用\_分割，先序遍历生成序列（树唯一）：

1\_2\_4\_\#\_\#\_\#\_3\_\#\_\#

再对右边：

2\_4\_\#\_\#\_\#。

我们只需要用kmp判断子树的字符串是否在其中就可以了

[20200604145034345.png]: https://img-blog.csdnimg.cn/20200604145034345.png
[20200604145316813.png]: https://img-blog.csdnimg.cn/20200604145316813.png
[20200604145337750.png]: https://img-blog.csdnimg.cn/20200604145337750.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200604150035893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200604152154951.png]: https://img-blog.csdnimg.cn/20200604152154951.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200604150842782.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020060415100279.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200604151134401.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200604154646117.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200604154744156.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[20200604154821196.png]: https://img-blog.csdnimg.cn/20200604154821196.png
[20200604155016256.png]: https://img-blog.csdnimg.cn/20200604155016256.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200604162221881.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70