首页 > 编程语言 >KMP算法

KMP算法

时间:2023-05-27 18:44:05浏览次数:54  
标签:匹配 int needle next 后缀 算法 KMP now

KMP算法

一 . 问题场景

有字符串A和字符串B,求B在A中首次出现的位置。力扣题目链接:28. 找出字符串中第一个匹配项的下标 - 力扣(LeetCode)

为方便说明,规定A为主串,B为子串(模式串)

二. 朴素的匹配算法

为方便说明,举A = "aabaaf",B="aaf"

使用如下图所示的算法(图中只显示了前两趟匹配)

朴素匹配算法演示

代码实现如下

class Solution {
    public int strStr(String haystack, String needle) {
        for(int index = 0; index <= haystack.length() - needle.length(); index++){
            int i = index;
            int j = 0;

            while(j <= needle.length() - 1){
                if(haystack.charAt(i) == needle.charAt(j)){
                    if(j == needle.length() - 1){
                        return index;
                    }
                    i++;
                    j++;
                }else{
                    break;
                }
            }
        }
        return -1;
    }
}

三. KMP算法

1.算法由来

因为是由这三位学者发明的:Knuth,Morris和Pratt,所以取了三位学者名字的首字母。所以叫做KMP

2.算法思想

在匹配主串aabaaf与子串aaf的第一趟匹配中,是在bf的位置发生的失配,说明前两个位置的字符是匹配上的。利用这个信息,我们可以在回溯时,不让index变为index + 1i往回退,而是只让j往回走。

如图所示

KMP算法原理图

如果在发生失配的模式串的前一部分,满足A1=A2,由于前一部分已经匹配上了,所以有B1=A1,B2=A2,所以有A1=B2,所以在下一次匹配时,应直接让i不动,j移动到n的位置进行匹配。每次发生失配时,j现在的位置 -> j之后的位置构成的映射可以用一个函数来表示,即next[j现在的位置] = j之后的位置,只要算出这个映射,接下来再在每次失配时根据映射next查找j应该在的位置,就完成了模式串匹配。

3.next求法

为求解next数组,规定字符串前缀:除最后一个字符外的其他字符构成的字符串;字符串后缀:除第一个字符外其他字符构成的字符串。字符串s的next数组为next[i] = s[0 : i + 1]的最长相等前后缀(s[i : j]为s中[i, j)的字符)。

3.1 手算过程

比如,对于aaabaaac

0处字符为a,没有前后缀,next[0] = 0;

1处字符为aa,前缀为a,后缀为a,最长相等前后缀为a,next[1] = 1;

......

6处字符为aaabaaa,前缀为aaabaa,后缀为aabaaa,找最长相等的前后缀过程(手算过程,机器实现不是这样,因为复杂度太高)

考虑aaabaaaabaaa,两者不同

考虑aaabaabaaa,两者不同

考虑aaabbaaa,两者不同

考虑aaaaaa,两者相同,所以最长相等前后缀为aaa,长度为3,next[6] = 3;

7处同理。

其next数组为{0, 1, 2, 0, 1, 2, 3, 0}

3.2 机算过程

显然上面手算方法的复杂度达到了O(N^2),不可取,应使用动态规划的方式进行求解。

求next[i]的值,分两种情况讨论

s[i] == s[now]和s[i] != s[now] (now = next[i - 1],即最长前缀的后一个位置)

用cpp写的伪代码如下(求解过程在注释中)

void getNext1(int* next, const string& s){
    next[0] = 0;
    //i指示是求谁的next数组
    for(int i = 1; i < s.length(); i++){
        //定义s[0: now]指的是{s[0], s[1], ..., s[now - 1]}

        //now指示最长前缀的后一个位置
        int now = next[i - 1];
        
        //step1(s[now] == s[i])
        //此时,在s[0 : i]中,有s[0 : now] == s[i - now : i],且为最长相等前后缀,长度为now   (next[i - 1] == now) (条件1)
        //如果s[now] == s[i],则有s[0 : now + 1] == s[i - now : i + 1]
        //假设在s[0 : i + 1]中,s[0 : now + 1]不是最长相等前缀,s[0 : now + 1 + t]才是
        //那么s[0 : now + 1 + t] == s[i - now - t : i + 1]
        //那么s[0 : now + t] == s[i - now - t : i],其长度为now + t,且为s[0 : i]中相等的前后缀
        //这与条件1矛盾
        //所以在s[0 : i + 1]中,s[0 : now + 1]是最长相等前缀,因此可以算得s[0 : i + 1]的最长相等前后缀长度为now + 1
        if(s[now] == s[i]){
            next[i] = now + 1;
            continue;
        }

        /*step2(s[now] != s[i])
        此时,在s[0 : i]中,有s[0 : now] == s[i - now : i],且为最长相等前后缀,长度为now   (next[i - 1] == now) (条件1)
        如果s[now] != s[i],就要减小now到k,使得s[0 : k] == s[i - k : i],k < now,求k值
        令next[now - 1] = t,显然t < now (条件2)
        则在s[0 : now]中,s[0 : t] == s[now - t : now] 
        又由条件1,s[0 : now] == s[i - now : i],
        所以,s[0 : t] == s[i - now : i - now + t] == s[i - t : i]
        即s[0 : t] == s[i - t : i],t < now
        所以t就是我们要的k,所以k = t = next[now - 1] (条件2),此时再比较s[k]是否==s[i],不等就继续到step2
        直到s[k] == s[i]或者k == 0
        */

        /*
        如果循环到最后s[k] == s[i],就使用step1的逻辑(即使是因为k == 0出来的也一样)
        如果循环到最后s[k] != s[i],说明到前后缀没有公共部分,取0即可
        */
        while(now >= 1 && s[now] != s[i]){
            now = next[now - 1];
        }
        if(s[now] == s[i]){
            next[i] = now + 1;
        }else{
            next[i] = 0;
        }
    }
}

4.匹配过程

匹配的过程如下所示

public int strStr(String haystack, String needle) {
        int[] next = getNext(needle);
        int i = 0; //指示主串
        int j = 0; //指示子串

        while(i < haystack.length()){
            if(haystack.charAt(i) == needle.charAt(j)){ //i与j匹配上了
                if(j == needle.length() - 1){ //i与j匹配到了子串末尾,说明匹配成功
                    return (i - needle.length() + 1);
                }
                i++;
                j++;
            }else{ //i与j没有匹配上
                //失配的位置不是needle[0]
                if(j != 0){
                    j = next[j - 1];
                }else{//失配的位置是needle[0]
                    i++;
                }
            }
        }

        return -1;
    }

5.完整代码

完整代码如下所示

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = getNext(needle);
        int i = 0; //指示主串
        int j = 0; //指示子串

        while(i < haystack.length()){
            if(haystack.charAt(i) == needle.charAt(j)){
                if(j == needle.length() - 1){
                    return (i - needle.length() + 1);
                }
                i++;
                j++;
            }else{
                //失配的位置不是needle[0]
                if(j != 0){
                    j = next[j - 1];
                }else{//失配的位置是needle[0]
                    i++;
                }
            }
        }

        return -1;
    }

    //求next数组
    public static int[] getNext(String s){
        int[] next = new int[s.length()];
        next[0] = 0;

        //求1到s.length() - 1的next,i为所求的next数组的位置
        for(int i = 1; i < next.length - 1; i++){
            //now始终为最长相同前后缀中,相同前缀的后一个位置
            int now = next[i - 1];

            //处理s[i] == s[now]
            if(s.charAt(i) == s.charAt(now)){
                next[i] = now + 1;
                continue;
            }

            //处理s[i] != s[now]
            while(now >= 1 && s.charAt(i) != s.charAt(now)){
                now = next[now - 1];
            }
            if(s.charAt(i) == s.charAt(now)){
                next[i] = now + 1;
            }else{
                next[i] = 0;
            }
        }

        return next;
    }
}

标签:匹配,int,needle,next,后缀,算法,KMP,now
From: https://www.cnblogs.com/tryingWorm/p/17437153.html

相关文章

  • 区块链应用:椭圆曲线数字签名算法ECDSA
    1椭圆曲线密码学椭圆曲线密码学(EllipticCurveCryptography,缩写ECC),是基于椭圆曲线数学理论实现的一种非对称加密算法。椭圆曲线在密码学中的使用是在1985年有NealKoblitz和VictorMiller分别提出来的。标准的椭圆曲线椭圆曲线加密考虑K=kG,其中K、G为椭圆曲线Ep(a......
  • 花朵识别系统Python实现,基于深度学习卷积神经网络算法
    一、背景花朵识别系统,基于Python实现,深度学习卷积神经网络,通过TensorFlow搭建卷积神经网络算法模型,并对数据集进行训练最后得到训练好的模型文件,并基于Django搭建可视化操作平台。在当今信息化社会,图像识别技术在各种领域都展现出了重要的应用价值,包括医学影像分析、自动驾驶、人脸......
  • 类欧几里得算法与万能欧几里得算法
    类欧几里得算法与万能欧几里得算法前置知识\(\lfloor\frac{a}{b}\rfloor\)表示\(a\)除以\(b\)向下取整的结果。在一定情况下,我们希望将带有「向下取整」的不等式转化为不带有「向下取整」的不等式。方便起见,在下面列出其公式,其中\(a,b,c,d\)均为整数:\[c\le\left......
  • m基于SPA和积译码算法的LDPC误码率matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下: 2.算法涉及理论知识概要       LDPC(Low-densityParity-check,低密度奇偶校验)码是由Gallager在1963年提出的一类具有稀疏校验矩阵的线性分组码(linearblockcodes),然而在接下来的30年来由于计算能力的不足,它一直被人......
  • JVM垃圾收集算法
    JVM垃圾收集算法当前商业虚拟机的垃圾收集器,大多数都遵循了“分代收集”(GenerationalCollection)的理论进行设计,分代收集名为理论,实质是一套符合大多数程序运行实际情况的经验法则,分代收集理论建立在两个分代假说之上:弱分代假说(WeakGenerationalHypothesis):绝大多数对象都是朝生......
  • m基于负价环N算法的无线传感器网络性能matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:     2.算法涉及理论知识概要负环的定义:负环是指权值和为负数的环。负环会使图的最短路径计算陷入死循环,因此,存在负环的图不存在最短路。 负环的计算方法:负环有两种计算方法,都是基于Bellman-Ford算法或者SPFA算法。第......
  • 基于QPSK调制和CoSaMP算法的信道估计均衡算法matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:    2.算法涉及理论知识概要 均衡器的分类    •均衡处理方法       时域均衡器:单载波数字通信中多采用时域均衡器,从时域的冲激响应考虑       正交频分复用OFDM调制:采用频域均衡    •是否......
  • 操作系统(3.4.2)--实时调度算法的分类
    按调度方式分类:非抢占式调度算法、抢占式调度算法1.非抢占式调度算法1)非抢占式轮转调度算法调度程序每次选择队列中的第一个任务投入运行。当时间片结束后,便把它挂在轮转队列的末尾,等待下次调度运行,而调度程序再选择下一个(队首)任务运行。这种调度算法可获得数秒至数十秒的响应时......
  • m基于FPGA的LDPC最小和译码算法verilog实现,包括testbench和matlab辅助验证程序
    1.算法仿真效果matlab2022a/vivado2019.2仿真结果如下:matlab仿真:0.5码率,H是4608×9216的矩阵。FPGA仿真:对比如下:2.算法涉及理论知识概要LDPC译码分为硬判决译码和软判决译码。硬判决译码又称代数译码,主要代表是比特翻转(BF)译码算法,它的实现比较简单,但是译码性能很差......
  • m基于负价环N算法的无线传感器网络性能matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要负环的定义:负环是指权值和为负数的环。负环会使图的最短路径计算陷入死循环,因此,存在负环的图不存在最短路。负环的计算方法:负环有两种计算方法,都是基于Bellman-Ford算法或者SPFA算法。第一种算法是:统计每个点的......