目录

Q1为什么主串不用回退 

Q2主串不会退，那我们的子串应该回退到哪里

next数组

怎么从next[i]推导出next[i+1]

①匹配得上的情况

②匹配不上的情况

C++代码

JAVA代码

Python代码

next数组的优化

对于传统的暴力匹配算法，我们是在匹配主字符串和子串的时候，一旦匹配不上，子串就回退到最初位置，主串也回退到与子串开始比较的位置。

这样的算法的时间复杂度会到达O(M*N)，也就是主串的长度乘以子串的长度

这里我们可以尝试让我们的主串中的指针不再回退，同时我们子串的指针在匹配的时候也回退到指定的位置，而不是开头的位置。

这里我们就需要用到我们的KMP算法

KMP算法的时间复杂度O(m+n)

Q1为什么主串不用回退 

 

 假设我们有上面两个字符串，第一个串为主串，第二个字符串为要匹配的子串

那么我们在从头开始匹配到下面这里的时候就会匹配不上

我们当前是从主串的0位置开始匹配的，但就算我们的主串的指针i回退到1的位置，进行下一轮匹配，也是不必要的，因为这里的主串中的1号位置的b跟我们子串的起始位置的元素（0号位置）a完全不一样！

Q2主串不会退，那我们的子串应该回退到哪里

 

 在我们的这里例子中，我们比较到这个位置的时候，发现我们的字符串匹配不上了

那么此时失败，我们不进行回退，因为在这个地方匹配失败，说明当前匹配到的位置前面，有一部分的的内容时相同的，不然这两个字符串不可能匹配到这个位置。

这里其实我们观察到，我们的子串要是回退到下标为2的位置就可以继续比较，因为我们主串的3,4位置和子串的0,1位置的内容其实是一样的，我们只需要接着比较主串的5号位置的元素和我们子串的2号位置的元素就可以了

 

 

next数组

KMP 的精髓就是 next 数组：也就是用 next[j] = k;来表示，不同的 j 来对应一个 K 值， 这个 K 就是你将来要移动的 j要移动的位置。而 K 的值是这样求的 

1、规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标字符结尾。
2、不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始；

练习 1： 举例对于“ababcabcdabcde”， 求其的 next 数组？

首先按照我们上面的做法，我们这里的第0号元素和第1号元素的下标分别为-1和0，

因为我们在0号位置是无法回退的，所以我们放置一个-1，来表示无法回退

我们在1号位置无法匹配，只能回退到0号位置，没有别的位置可以回退！

 

然后我们计算主串下标为2的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a和ab。

当前我们的j等于2

以j-1下标，也就是以字符串[1]位置为字符结尾的字符串有b和ab。

这里只有ab是能够匹配上的

所以我们就只能回退到初始的位置才能够匹配上，也就是回退到0的位置。

 

 然后我们计算主串下标为3的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a，ab和aba。

当前我们的j等于3

以j-1下标，也就是以字符串[2]位置为字符结尾的字符串有a，ba，aba。

这里有a和aba是能够匹配上的

如果是aba的话我们需要回退到开头，如果是a的话，也就是说我们只需要回退到1的位置就可以了。

因为我们的当前的主字符串的2的位置和我们的主字符串的0位置都是a，所以我们接下来从1的位置再继续匹配就可以了

 

然后我们计算主串下标为4的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a，ab，aba，abab。

当前我们的j等于4

以j-1下标，也就是以字符串[3]位置为字符结尾的字符串有b,ab,bab,abab。

这里有ab是能够匹配上的（非abab，否则就是从最初始位置重新匹配）

因为我们这里假设的是4位置匹配不上的话，但是就是代表着0-3的位置式能够成功匹配上的那么又因为0和1与2和3是一样的，所以我们就直接回退到2的位置继续比较就可以了

 

 

然后我们计算主串下标为5的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a，ab，aba，abab，ababc。

当前我们的j等于5

以j-1下标，也就是以字符串[4]位置为字符结尾的字符串有c,bc,abc,babc,ababc。

这里有ababc是能够匹配上的，所以我们这里需要回退到最初始的位置，也就是0下标

然后我们计算主串下标为6的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a，ab，aba，abab，ababc，ababca。

当前我们的j等于6

以j-1下标，也就是以字符串[5]位置为字符结尾的字符串有a,ca,bca,abca,babca,ababca。

这里有a是能够匹配上的，所以我们这里需要回退到1下标

  

 

 

然后我们计算主串下标为7的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a，ab，aba，abab，ababc，ababca，ababcab。

当前我们的j等于7

以j-1下标，也就是以字符串[6]位置为字符结尾的字符串有b，ab，cab，bcab，abcab，babcab，ababcab。

这里有ab是能够匹配上的，所以我们这里需要回退到2下标

 

 

然后我们计算主串下标为8的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a，ab，aba，abab，ababc，ababca，ababcab，ababcabc。

当前我们的j等于8

以j-1下标，也就是以字符串[7]位置为字符结尾的字符串有c，bc，abc，cabc，bcabc，abcabc，babcabc，ababcabc。

这里有ababcabc是能够匹配上的，所以我们这里需要回退到0下标

 

然后我们计算主串下标为9的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串有a，ab，aba，abab，ababc，ababca，ababcab，ababcabc，ababcabcd。

当前我们的j等于9

以j-1下标，也就是以字符串[8]位置为字符结尾的字符串有d，cd，bcd，abcd，cabcd，bcabcd，abcabcd，babcabcd，ababcabcd。

这里有ababcabcd是能够匹配上的，所以我们这里需要回退到0下标

 

然后我们计算主串下标为10的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串

有a，ab，aba，abab，ababc，ababca，ababcab，ababcabc，ababcabcd，ababcabcda。

当前我们的j等于10

以j-1下标，也就是以字符串[9]位置为字符结尾的字符串

有a，da，cda，bcda，abcda，cabcda，bcabcda，abcabcda，babcabcda，ababcabcda。

这里有a是能够匹配上的，所以我们这里需要回退到1下标

 

 

然后我们计算主串下标为11的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串

有a，ab，aba，abab，ababc，ababca，ababcab，ababcabc，ababcabcd，ababcabcda，ababcabcdab。

当前我们的j等于11

以j-1下标，也就是以字符串[10]位置为字符结尾的字符串

有b，ab，dab，cdab，bcdab，abcdab，cabcdab，bcabcdab，abcabcdab，babcabcdab，ababcabcdab。

这里有ab是能够匹配上的，所以我们这里需要回退到2下标

 

 

 

然后我们计算主串下标为12的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串

有a，ab，aba，abab，ababc，ababca，ababcab，ababcabc，ababcabcd，ababcabcda，ababcabcdab，ababcabcdabc。

当前我们的j等于12

以j-1下标，也就是以字符串[11]位置为字符结尾的字符串

有c，bc，abc，dabc，cdabc，bcdabc，abcdabc，cabcdabc，bcabcdabc，abcabcdabc，babcabcdabc，ababcabcdabc。

这里有ababcabcdabc是能够匹配上的，所以我们这里需要回退到0下标

 

然后我们计算主串下标为13的next数组的位置应该是什么

这里我们按照我们上面的说法：

我们需要找到一个以下标 0 字符开始的字符串，和另一个以 j-1 下标字符结尾的字符串。

这里以下标0开始的字符串

有a，ab，aba，abab，ababc，ababca，ababcab，ababcabc，ababcabcd，ababcabcda，ababcabcdab，ababcabcdabc，ababcabcdabcd。

当前我们的j等于13

以j-1下标，也就是以字符串[12]位置为字符结尾的字符串

有d，cd，bcd，abcd，dabcd，cdabcd，bcdabcd，abcdabcd，cabcdabcd，bcabcdabcd，abcabcdabcd，babcabcdabcd，ababcabcdabcd。

这里有ababcabcdabcd是能够匹配上的，所以我们这里需要回退到0下标

 

OK，这里我们就知道我们的next数组是怎么生成的了。

怎么从next[i]推导出next[i+1]

到这里大家对如何求next数组应该问题不大了，接下来的问题就是，已知next[i] = k;怎么求next[i+1] = ?
如果我们能够通过 next[i]的值,通过一系列转换得到 next[i+1]得值，那么我们就能够实现这部分。
那该怎么做呢？

①匹配得上的情况

首先假设： next[i] = k 成立，那么

（我们匹配的规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标字符结尾。）

就有这个式子成立： P0...Pk-1 = Px...Pi-1;

                       得到： P0...Pk-1 = Pi-k..Pi-1;

 也就是说我们当前在判断Pi和Pk的位置能不能匹配上
到这一步：我们再假设如果 Pk = Pi;

我们可以得到 P0...Pk = Pi-k..Pi;

那这个就是 next[i+1] = k+1; 

也就是说我们只需要回退到k+1的位置

在我们上面的这个情况中

我们的p[i]也就是p[4]="b"

我们的p[k]也就是p[1]="b"

此时的next[i+1]也就是next[4+1]=next[5]=k+1也就是2

所以我们的next[5]=2

②匹配不上的情况

 在我们上面的这个情况中

我们的p[i]也就是p[5]="a"

我们的p[k]也就是p[2]="c"

我们的p[i]!=p[k]

那么k要继续回退到0的下标（这里我们的k是2）

也就是k_new=next[k]进行回退，得到了k_new=0

进一步回退后，我们的

p[0]="a"

p[i]也就是p[5]="a"

我们的这时p[0]==p[i]，那么我们就已经匹配上了！可以停止回退了！

因为我们的第0的位置已经匹配上了，所以我们接着匹配下一个位置，也就是1号位置

next[i+1]=k_new+1

也就是next[6]=0+1=1

C++代码

#include <assert.h>
//编写我们的next数组
void GetNext(int *next,const char *sub)
{
    int lensub = strlen(sub);
    //next数组的第0号位置一定是-1，第1号位置一定是0
    next[0] = -1;
    next[1] = 0;
    //i是我们的匹配串的位置的指针
    int i = 2;//下一项
    //K是要回退的位置
    int k = 0;//前一项的K
    while(i < lensub)//next数组还没有遍历完
    {
        // 如果我们的k==-1，也就是我们已经回退到了0号位置的元素，再回退就不能回退了，
        // 进入下面的if判断内容，将我们的next[i]变成k+1也就是0，也就是回退到0的位置

        //然后第二种情况，如果我们的sub[k]==sub[i-1]，也就是和我们上面所画的图中Pk和Pi的位置相同的情况
        //（这里由于我们的i所指向的是下一项，也就是上面我们图中画的是pi的位置，我们这里代码中其实应该是pi-1的位置）
        //置于这里我们为什么要设置i为要填写的下一项的位置呢？因为我们最初始的两个next已经设置过了，分别为-1和0
        //当然我们也可以修改我们上面的i，最初是为1，那么我们这里的sub[i-1]就可以改成sub[i]，这种写法也是可以的
        //这种情况是将我们的i指针++，并且将k++，因为我们当前位置又匹配上了，所以接着匹配后面的
        if((k == -1) || sub[k] == sub[i-1])//
        {
            //这里我们为什么要k+1，因为我们的k位置所对应的位置已经匹配上了，所以我们需要从k+1的位置继续匹配
            //这跟我们上面的分析是一样的！
            next[i] = k+1;
            i++;
            k++;//k = k+1???//下一个K的值新的K值
        }
        else
        {
            //如果我们匹配不上的话，我们就需要回退。
            //这里的k是我们上一轮的出来的，也就是我们的当前要判断next数组回退位置的上一个位置的k
            //那么我们当前位置的k其实就是回退之后的结果，也就是next[k]位置的位置。
            k = next[k];
        }
    }
}
//第一个参数为主串，第二个参数为子串，第三个参数为从主串的第几个位置开始
int KMP(const char *s,const char *sub,int pos)
{
    //目标
    int i = pos;
    int j = 0;
    int lens = strlen(s);
    int lensub = strlen(sub);
    //开辟皮next数组
    int *next = (int *)malloc(lensub*sizeof(int));//和子串一样长
    assert(next != NULL);
    //获取到next数组
    GetNext(next,sub);
    while(i < lens && j < lensub)
    {
        //第一种情况
        //这里的j==-1是我们下面的next数组如果next[j]=-1了，那么也就是需要从子串的第一个元素进行匹配
        //所以我们序进入我们的if重新进行匹配
        
        //第二种情况
        //我们的主串和子串匹配得上，我们就同时向后移动我们的主串和子串的两个指针
        if((j == -1) || (s[i] == sub[j]))
        {
            i++;
            j++;
        }
        else
        {
            //我们的子串回退到我们next的数组中指向的位置
            j = next[j];
        }
    }
    free(next);
    if(j >= lensub)
    {
        return i-j;
    }
    else
    {
        return -1;
    }
}
int main()
{
    char *str = "ababcabcdabcde";
    char *sub = "abcd";
    //分别传入我们的主串和子串，并且从0的位置开始匹配
    printf("%d\n",KMP(str,sub,0));
    return 0;
}

JAVA代码

 

public static void getNext(int[] next, String sub){
        next[0] = -1;
        next[1] = 0;
        int i = 2;//下一项
        int k = 0;//前一项的K
        while(i < sub.length()){//next数组还没有遍历完
            if((k == -1) || sub.charAt(k) == sub.charAt(i-1)) {
                next[i] = k+1;
                i++;
                k++;
            }else{
                k = next[k];
            }
        }
    }
    public static int KMP(String s,String sub,int pos) {
        int i = pos;
        int j = 0;
        int lens = s.length();
        int lensub = sub.length();
        int[] next= new int[sub.length()];
        getNext(next,sub);
        while(i < lens && j < lensub){
            if((j == -1) || (s.charAt(i) == sub.charAt(j))){
                i++;
                j++;
            }else{
                j = next[j];
            }
        } if(j >= lensub) {
            return i-j;
        }else {
            return -1;
        }
    }
    public static void main(String[] args) {
        System.out.println(KMP("ababcabcdabcde","abcd",0));
        System.out.println(KMP("ababcabcdabcde","abcde",0));
        System.out.println(KMP("ababcabcdabcde","abcdef",0));
    }

Python代码

from SqString import SqString
MaxSize=100
def GetNext(t,next):        	    #由模式串t求出next值
    i, k = 0, -1
    next[0] = -1
    while i < t.getsize() - 1:
        if k == -1 or t[i] == t[k]:  # j遍历后缀，k遍历前缀
            i, k = i + 1, k + 1
            next[i] = k
        else:
            k = next[k]

def KMP(s,t):                       #KMP算法
    next = [None] * MaxSize
    GetNext(t, next)  # 求next数组
    i, j = 0, 0
    while i < s.getsize() and j < t.getsize():
        if j == -1 or s[i] == t[j]:
            i, j = i + 1, j + 1  # i,j各增1
        else:
            j = next[j]  # i不变,j回退
    if j >= t.getsize():
        return (i - t.getsize())  # 返回起始序号
    else:
        return (-1)  # 返回-1


if __name__ == '__main__':
    cstr1="aaaaab"
    s=SqString()
    s.StrAssign(cstr1)
    print("s: ",end='');s.DispStr()
    
    cstr2="aaab"
    t=SqString()
    t.StrAssign(cstr2)
    print("t: ",end='');t.DispStr()

    print("KMP: %d" %(KMP(s,t)))

next数组的优化

next 数组的优化，即如何得到 nextval 数组：

有如下串： aaaaaaaab,

他的 next 数组是-1,0,1,2,3,4,5,6,7.

我们观察到如果我们的8号位置匹配失败了，我们需要回退到7号位置，然后回退到6号，以此类推，最终回退到-1的位置

这样非常不方便！！
而修正后的数组 nextval 是：
-1， -1， -1， -1， -1， -1， -1， -1， 7。

这样我们就能直接一步回退到-1了，不用一次次迭代了！

nextval的数组求法就是如果当前要回退的位置和当前的字符一样，那么救写那个字符的nextval值，不一样就写自己的！

在上面的例子中：4下标的a，应该回退到3号位置，3号位置还是a。所以，nextval值就是直接是3号位置的-1

但是8下标的b，应该回退到7号位置，但是7号位置式'a'不是我们的8号位置的'b'，所以我们的8号位置就写它自己的7

#include <assert.h>
//编写我们的next数组
void GetNext(int *next,const char *sub)
{
    int lensub = strlen(sub);
    //next数组的第0号位置一定是-1，第1号位置一定是0
    next[0] =-1;
    int k;
    if(sub[1]==sub[0])
    {
        next[1]=-1;
        k = -1;//前一项的K
    }else
    {
        next[1] = 0;
        k = 0;//前一项的K
    }
    //i是我们的匹配串的位置的指针
    int i = 2;
    //K是要回退的位置
    while(i < lensub)//next数组还没有遍历完
    {
        // 如果我们的k==-1，也就是我们已经回退到了0号位置的元素，再回退就不能回退了，
        // 进入下面的if判断内容，将我们的next[i]变成k+1也就是0，也就是回退到0的位置

        //然后第二种情况，如果我们的sub[k]==sub[i-1]，也就是和我们上面所画的图中Pk和Pi的位置相同的情况
        //（这里由于我们的i所指向的是下一项，也就是上面我们图中画的是pi的位置，我们这里代码中其实应该是pi-1的位置）
        //置于这里我们为什么要设置i为要填写的下一项的位置呢？因为我们最初始的两个next已经设置过了，分别为-1和0
        //当然我们也可以修改我们上面的i，最初是为1，那么我们这里的sub[i-1]就可以改成sub[i]，这种写法也是可以的
        //这种情况是将我们的i指针++，并且将k++，因为我们当前位置又匹配上了，所以接着匹配后面的
        if((k == -1) || sub[k] == sub[i-1])//
        {
            //这里我们为什么要k+1，因为我们的k位置所对应的位置已经匹配上了，所以我们需要从k+1的位置继续匹配
            //这跟我们上面的分析是一样的！

            i++;
            k++;//k = k+1???//下一个K的值新的K值
            if (sub[i-1]!=sub[k])
            {
                next[i-1]=k+1;
            }else
            {
                next[i-1] = next[k];
            }
        }
        else
        {
            //如果我们匹配不上的话，我们就需要回退。
            //这里的k是我们上一轮的出来的，也就是我们的当前要判断next数组回退位置的上一个位置的k
            //那么我们当前位置的k其实就是回退之后的结果，也就是next[k]位置的位置。
            k = next[k];

        }
    }
}
//第一个参数为主串，第二个参数为子串，第三个参数为从主串的第几个位置开始
int KMP(const char *s,const char *sub,int pos)
{
    //目标
    int i = pos;
    int j = 0;
    int lens = strlen(s);
    int lensub = strlen(sub);
    //开辟皮next数组
    int *next = (int *)malloc(lensub*sizeof(int));//和子串一样长
    assert(next != NULL);
    //获取到next数组
    GetNext(next,sub);
    cout<<"我们的next数组为"<<endl;
    for(int i=0;i<lensub;i++)
    {
        cout<<next[i]<<" ";
    }
    cout<<endl;
    while(i < lens && j < lensub)
    {
        //第一种情况
        //这里的j==-1是我们下面的next数组如果next[j]=-1了，那么也就是需要从子串的第一个元素进行匹配
        //所以我们序进入我们的if重新进行匹配

        //第二种情况
        //我们的主串和子串匹配得上，我们就同时向后移动我们的主串和子串的两个指针
        if((j == -1) || (s[i] == sub[j]))
        {
            i++;
            j++;
        }
        else
        {
            //我们的子串回退到我们next的数组中指向的位置
            j = next[j];
        }
    }
    free(next);
    if(j >= lensub)
    {
        return i-j;
    }
    else
    {
        return -1;
    }
}
int main()
{
    char *str = "aaaaaaaaaaaaab";
    char *sub = "aaaaaab";
    //分别传入我们的主串和子串，并且从0的位置开始匹配
    printf("%d\n",KMP(str,sub,0));
    return 0;
}

 在上面的代码中，我们顺便把next数组打印出来看一下

 

 也就是我们优化之后的结果

# 数据结构 # 算法 # leetcode
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

以智能 致世界 | 操作系统大会2024议程全览

avatar 开放原子开发者工作坊

开放原子开源基金会新增捐赠人（2024年9月）

2024年9月，新增以下单位成为开放原子开源基金会及旗下项目捐赠人。

avatar 开放原子开发者工作坊

2024开放原子开发者大会议题征集正式开启

2024开放原子开发者大会（以下简称“大会”）将于12月中旬重磅来袭,2024开放原子开发者大会议题征集正式开启!

avatar 开放原子开发者工作坊