目录

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数组打印出来看一下

 

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

Logo

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

更多推荐