KMP算法——寻找子串位置

1、KMP算法简介：

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度时间复杂度)O(m+n)。

2、什么是字符串匹配：

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

在Java中就是String的indexOf()方法。

3、对比暴力法和KMP算法：

首先我们可以比对一下暴力法和KMP算法的差距：

（1）暴力法

挨个截取遍历字符串，然后对比

image.png

（2）KMP算法

若遇到不匹配的，则会跳转到最小公共子串以后的地方进行匹配，会跳过中间不匹配的步骤，从而简化了时间复杂度。但是也都是空间换时间

image.png

这块声明一下，暴力法中的每一个字符匹配（连接的黑色剪头）是挨个匹配的，我是写到了一起，其实是很多步的；而KMP是直接跳转到最后一步的，跳过了公共子串的判断，可能是案例比较经典，跳转过来之后，就可以直接排除当前情况了。

感受玩KMP算法的魅力，现在开始操作起来，接收这愉快的“解题”环节（更像是受虐）。

4、KMP算法实现：

KMP算法一般分为两步：

1. 提取加速匹配的信息（构造next数组），也是本算法中最难的部分。
2. 字符串的匹配

4.1、提取加速匹配的信息（构造next数组）

KMP之所以可以跳过很多公共子串的匹配，是因为它的next数组里面记录了从当前下标位置，往前判断，找到最长公共子串的最后一个位置。

用数学语言表述：本文中的最小公共子串的概念，不是官方的定义，就自己读起来顺畅。

对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t0 开头的 k 个字符

依次与 t j 前面的 k

，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。

图解：

image.png

对于元素t5，存在一个实数2，使得模式串t0开头的2个字符 t0 t1，依次与t3和t4相同。

如果在匹配过程中，到t5的时候，和目标串不匹配了，此时就可以模式串回调到t2的位置，接着判断匹配。

因为t0 t1 是最大重复子串，所以就可以跳过判断，直接判断t2和当前目标字符串的字符是否匹配。

图解：

image.png

首先，先需要了解一下next数组，存放的是什么东西？

next数组其实就是存放着一个回调的位置，意思就是如果我匹配模式串的时候，假如到 t[i] 位置的时候不匹配了，那么我应该跳转到那个位置，接着对比匹配，可以跳过重复子串的判断。

例如上述案例，next[5] = 2

注意：next数组只和模式串有关系，和目标串没有关系。就算没有目标串，模式串也有next数组。

如果看到这块，你能够理解next的功能，恭喜你，你已经完成成功路程的一半了。

下来我们来一起探索一下，next数组应该如何得到？

首先，先拿到我们的模式串：我们的next数组的大小就是模式串pat的长度。

image.png

分为如下三种情况，来计算next的值：

我们用j来遍历模式串pat，初始值为0，用k作为临时变量，初始值为-1，来计算next[j]的值。

我们可以根据上面的理解可以直接写出来，next数组，但是，要怎样设置算法让计算机计算呢？

image.png

（1）特殊情况：

当j为0的时候，，next[0] = -1，目的是方便我们后面的计算。

当j为1的时候，pat[0]就是他的最小子串，所以next[1] = 0;

（2）当 pat[j] == pat[k] 或者 k == -1 的情况:

说明目前遍历到字符串为首元素，或者就是遍历到的字符和k所指向的位置元素相同，每次都是从字符串串首开始的，所以k的含义，不仅是记录下标位置，还有最长公共子串的长度。

这块的最长公共子串，是自己的定义，意思是pat[0] pat[1]…… pat[k] 字符串和 pat[j-k] pat[j-k+1]…… pat[j] 相同。

image.png

遇到这种情况，就让j++，k++，next[j] = k

这块注意，为什么我们判断的是pat[j] == pat[k]，而要给next[j] = k++，因为我们next里面存放的是遇到不匹配的时候，要回调的位置，因为0到k的位置已经是匹配的了，所以我们直接跳转到k+1的位置，我们就给next[j] = k++。

（3）其他情况：也就是k的位置与j的位置不匹配

我们直到如果不匹配的话，就需要调用回调，让k的值回调。我们计算的next数组就是用来回调的。

让 k = next[k]

让k回调了之后，再次进入循环，若k的位置与j的位置还是不匹配，那么k就继续回调，直到k=-1，会满足第二种情况，即给next[j] = 0。

因为逻辑性很强，所以希望参考代码理解。

代码：

void Getnext(int next[],String pat)
{
    if(pat.length()==0) {
            next = new int[]{0};
            return;
    }
    next = new int[pat.length()];
    int j = 0, k = -1;
    next[0] = -1;
    while (j < pat.length() - 1) {
        if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
            j++;
            k++;
            next[j] = k;     
        } else
            k = next[k];     //k回调
    }
}

4.2 字符串的匹配

当我们拿到next数组的时候，后面使用的时候会十分简单！！！

我们用 i 和 j 分别遍历 目标字符串s和模式串pat

我们这次只需要一个单层循环，这也是和暴力法降低时间复杂度最根本的地方。

单层循环：while( i<s.length()&&j<pat.length() )

• 当s[i] == pat[j] 时，说明当前的字符匹配，i++;j++；
• 当s[i] != pat[j] 时，说明当前的字符不匹配，让j进行回调，即 j = next[j];

不满足条件退出循环

• 当j>=pat.length()时，说明已经找到模式匹配的子串了，直接return 找到的位置，即return i-pat.length();
• 否则，说明没有找到模式匹配的子串，直接 return -1;

代码：

    public int indexOf(String s)
    {
        if(pat.length()==0) {
            return 0;
        }
        int i=0,j=0;

        while(i<s.length()&&j<pat.length())
        {
            if(j==-1 || s.charAt(i) == pat.charAt(j))
            {
                i++;
                j++;
            }
            else j=next[j];               //j回调
        }
        if(j>=pat.length())
            return (i-pat.length());         //匹配成功，返回子串的位置
        else
            return (-1);                  //没找到
    }

5、KMP完整代码：

    void Getnext(int next[], String pat) {
        next = new int[pat.length()];
        int j = 0, k = -1;
        next[0] = -1;
        while (j < pat.length() - 1) {
            if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
                j++;
                k++;
                next[j] = k;
            } else
                k = next[k]; // k回调
        }
    }

    int indexOf(String s) {
        int i = 0, j = 0;

        while (i < s.length() && j < pat.length()) {
            if (j == -1 || s.charAt(i) == pat.charAt(j)) {
                i++;
                j++;
            } else
                j = next[j]; // j回调
        }
        if (j >= pat.length())
            return (i - pat.length()); // 匹配成功，返回子串的位置
        else
            return (-1); // 没找到
    }

6、利用面向对象封装

package com.company.project.arithmetic;

public class KMP {

    private int[] next;
    private String pat;

    /**
     * 在构造方法中计算next数组
     * @param pat 模式串
     */
    public KMP(String pat) {
        this.pat = pat;
        if(pat.length()==0) {
            next = new int[]{0};
            return;
        }
        next = new int[pat.length()];
        int j = 0, k = -1;
        next[0] = -1;
        while (j < pat.length() - 1) {
            if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
                j++;
                k++;
                next[j] = k;
            } else
                k = next[k];
        }
        
    }

    /**
     * 寻找子串位置
     * @param s 目标串
     * @return
     */
    public int indexOf(String s) {
        if(pat.length()==0) {
            return 0;
        }
        int i = 0, j = 0;

        while (i < s.length() && j < pat.length()) {
            if (j == -1 || s.charAt(i) == pat.charAt(j)) {
                i++;
                j++;
            } else
                j = next[j]; // j回退。。。
        }
        if (j >= pat.length())
            return (i - pat.length()); // 匹配成功，返回子串的位置
        else
            return (-1); // 没找到
    }

    public static void main(String[] args) {
        KMP kmp = new KMP("");
        for (int i = 0; i < kmp.next.length; i++) {
            System.out.println(kmp.next[i]);
        }
        String s = "abababcabd";
        System.out.println("result:" + kmp.indexOf(s));
    }
}