否则，将 k更新为 next[k]

发布时间：2025-06-24 20:36:54  作者：北方职教升学中心  阅读量：008


这只是我们通过观察得出的结论，如果每次都要重新找最长公共真前后缀，又会浪费大量时间。创建 next 数组

  1. 为模式串 s2开辟长度为 s2.length的空间。

    3.1. 算法原理

    在介绍算法原理之前，我们要先了解几个新概念。

    2. 3. KMP算法

    KMP算法是三位学者(Knuth-Morris-Pratt )在 Brute-Force算法的基础上同时提出的模式匹配的改进算法。

    3.5.1. 未优化之前

    未优化前的KMP算法步骤如下：

    一、然后由问题一得s2[0,k1-1]=s2[k-k1,k-1]=s2[j-k1,j-1]，最后问题就转化为在[0,k-1]的区间中寻找长度为k1的最长公共前后缀，即k1 = next[k]。

    通过上述列子，我们不难发现出现这种情况是因为当回退下标k=next[j]时，如果s2[k]=s2[j]，又因为s2[j]!=s1[i]，自然s2[k]!=s1[i]。

  2. 最后再比较s2[k1]与s2[j]，如果相等，则next[j+1]=k1+1。其中s1是文本串，s2为子串，即从s1中匹配s2。
  3. 如果匹配成功则返回文本串匹配成功开始的下标。**那么j下标该回退到哪一个位置呢？我们可以来看一下下图：

    img

    从上述观察我们不难发现，如果匹配失败，i如果不回退，j就要回退到e的下标继续匹配。

  4. 空间复杂度：动态开辟了一个nextval数组，空间复杂度为O(N)。也就是说s1[0,i-1]=s2[0,j-1]，而s2[0,p1]与s2[j-1-p1,j-1]又是最长公共真前后缀。

2.3. 代码实现

下面是具体的代码实现，其中串是以顺序串的形式实现。

img

  1. 问题二：为什么s2[k]!=s2[j]后，就可以通过不断更新kn=next[k-1]，再比较s2[kn]==s2[j]就能得到新的最长公共真前后缀？
  1. 首先当s2[k]!=s2[j]后，新的最长公共真前后缀的长度一定不大于k(假设长度len大于k，因为s2[k]!=s2[j]，所以len>k+1即s2[0,len]=s[j-len,j]=>s2[0,len-1]=s[j-len,j-1]=>next[j]=len>k，又因为next[j]=k，所以矛盾)。

    下面我们将选取两个最经典的BF与KMP算法为大家演示。由此，衍生了一系列的算法(如BF，BM，RK，KMP)就是我们的字符串匹配算法。

    所以就可以推出一定存在x使得s1[x,i-1]=s2[0,p1]=s2[j-1-p1,j-1]。匹配过程

    1. 分别使用两个下标 i和 j指向文本串与模式串。其实特别简单，我们要知道j下标如果从零开始就代表成功匹配的个数。所以i-起始位置1=j-起始位置2=>起始位置1=i-j。
      1. 最后当j移动至末尾证明匹配成功，返回s1成功的匹配成功的起始下标。
      2. 否则，将 k更新为 next[k]。s2[j-k,j-1]同理也可以分解出两个相同真前后缀s2[j-k,j-k+k1-1]=s2[j-k1,j-1]。只需要回退模式串s2的下标，就能重新开始匹配，自然文本串的i下标就不用回退了。

        那么既然s1的下标不回退，自然是**回退模式串s2的下标j。

        ✨✨ 欢迎大家来到贝蒂大讲堂✨✨

        🎈🎈养成好习惯，先赞后看哦~🎈🎈

        所属专栏：数据结构与算法
        贝蒂的主页：Betty’s blog

        1. 什么是字符串匹配算法

        字符串匹配是计算机科学中的一个基础概念，广泛应用于文本处理、

      3. 最长公共真前后缀：最长相等的真后缀与真前缀，例如"abcdab"的最长公共前后缀就是"ab"。

3.4. 算法优化

虽然上述的算法在绝大数情况下运算速率都比较优秀，但是也许考虑一些特殊情景，比如说下面这种情况。这里我们以最坏的情况作为参考，所以时间复杂度为O(NM)。它的目的是在一个给定的文本串中寻找指定子串是否存在。所以我们可以采取另一种方式：

首先我们先规定next[0]=-1，next[1]=0。

KMP算法在上述情况下,文本串位置不需要回退,从而可以大大提高效率

​ -------以上摘自百度百科

3.2. 图例演示

KMP算法一个非常重要的思想就是指向文本串s1的下标i不回退，以此来解决BF算法i不断回退造成大量时间消耗的问题。

img

然后因为k1=next[k]，我们可以将s2[0,k-1]分解成两个相同的真前后缀s2[0,k1-1]=s2[k-k1,k-1]。数据挖掘、最坏的时间复杂度为O(NM)，即找不到或者在最后才找到。

img

3.5. 代码实现

我们的代码将基于前面学习的数组串来实现。

img

  • 这里我们就需要思考一个问题，匹配失败如何返回s1的下一个位置重新匹配。匹配成功将i下标与j下标往后移，继续匹配，并且k也需要递增。
  • 真前缀：除了字符串s本身之外的前缀。搜索引擎等领域。

    • img

    1. 相等则继续匹配，否则从s1的下一个位置重新开始匹配。所以又可以记作s2[0,p1]=s2[j-1-p1,j-1]。

      ​ -------以上摘自百度百科

      2.2. 图例演示

      上面的文字可能过于抽象，我们可以通过图示来为大家演示一下算法流程。next[j] = k含义也就是在[0,j-1]区间中，最长公共真前后缀的长度为k。这个我们就之存入一个数组中方便取用，这就是我们的next数组。证明如下：

  1. 问题一：如何推出s2[0,k1-1]=s2[k-k1,k-1]=s2[j-k,j-k+k1-1]?

首先由条件得s2[0,k-1]=s2[j-k,j-1]，并且s2[0,k-1]，s2[j-k,j-1]都能继续分出最长公共真前后缀(不能划分时，kn=-1）。

二、

  • 若匹配失败，将 j下标回到 next数组对应的位置。
  • 开始遍历：
    • 若匹配相同，或者 j == -1，则让两个下标右移以匹配下一个字符。

      img

      如果出现上述情况，模式串s2的下标会依次从4->3->2->1->0。我们不妨设k1=next[k]，因为s2[0,k-1]=s2[j-k,j-1]，所以推出s2[0,k1-1]=s2[k-k1,k-1]=s2[j-k,j-k+k1-1]=s2[j-k1,j-1]，**如果此时s2[k1] = s2[j]，则s2[0,k1]=s2[j-k1,j]，就可以知道新的最长公共真前后缀为k1+1，即next[j]=k1+1，否则设k2=next[k1]继续重复上述过程，若存在kn=-1，循环结束让next[j]=0即k0+1。

    • 反之，如果找不到匹配，则返回 -1。其实我们想我们的模式串s2每一个位置都有可能匹配失败，那么每个位置都应该有一个与之对应的回退下标。又因为两个原串相等，所以这这四个子串相等，s2[0,k1-1]=s2[k-k1,k-1]=s2[j-k,j-k+k1-1]=s2[j-k1,j-1]。

      • 后缀：是指从串某个位置i开始到整个串末尾结束的一个特殊子串。

        nextval数组是在原来next数组的基础上增加一个判断条件，即若s2[k]=s2[j],就让nextval[j]更新成nextval[k]实现一步到位的结果，从而节约效率。

    如果不相等，则重复上述过程，最后如果kn=-1，循环结束让next[j]=0即k0+1。

    intBF(Sstring*s1,Sstring*s2){assert(s1 &&s2);intlen1 =StrLength(s1);intlen2 =StrLength(s2);if(len1 ==0||len2 ==0){return-1;}inti =0;//文本串下标intj =0;//子串下标while(i <len1 &&j <len2){if(s1->data[i]==s2->data[j])//匹配成功{i++;j++;}else{j =0;i =i -j +1;}}if(j >=len2)//匹配失败{returni -j;}return-1;}

    2.4. 复杂度分析

    我们用M表示文本串的长度，N表示子串的长度。

    2. BF算法

    2.1. 算法原理

    BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。所以s2[0,k]=s2[j-k,j]，k+1显然也是最长公共真前后缀=>next[j+1]=k+1。BF算法是一种蛮力算法。记为s[0，i]，例如"abc"就是字符串"abcadb"的一个前缀。

  • 真后缀：除了字符串s本身之外的后缀。

    • img

    1. 第二步求回退下标k，k的值就是模式串前缀的下一个位置p1+1，所以k=p1+1。然后一直重复上述过程。记为s[i,s.length-1]，例如"adb"就是字符串"abcadb"的一个后缀。
    int*GetNext(Sstring*s2){char*str2 =s2->data;intlen =StrLength(s2);int*next =(int*)malloc(sizeof(int)*len);//开辟空间if(next ==NULL){perror("malloc fail:");returnNULL;}next[0]=-1;inti =1;//当前下标intk =-1;//前一项的kwhile(i<len){//kn=-1或者情况一if(k==-1||str2[i -1]==str2[k]){next[i]=k +1;i++;k++;}else{//情况二k =next[k];}}returnnext;}intKMP(Sstring*s1,Sstring*s2,intpos){//首先判断边界条件assert(s1 &&s2);intlen1 =StrLength(s1);intlen2 =StrLength(s2);if(len1 ==0||len2 ==0){return-1;}if(pos <0&&pos >=len1){return-1;}int*next =GetNext(s2);inti =pos;intj =0;while(i <len1 &&j <len2){if(j ==-1||s1->data[i]==s2->data[j]){i++;j++;}else{j =next[j];//更新至next数组}}if(j >=len2)//参考BF实现逻辑{returni -j;}free(next);//释放内存return-1;}
    3.5.2. 优化之后

    优化之后步骤与之前类似，相较于优化之前，优化后更新nextval时需判断此时的s2[j]是否等于s2[k+1]，等于nextval[i] = nextval[k+1]，否则nextval[i] = k + 1。所以说x~i-1就是能在模式串s2中从起始位置匹配的最长长度。

    int*GetNext(Sstring*s2){char*str2 =s2->data;intlen =StrLength(s2);int*nextval =(int*)malloc(sizeof(int)*len);//开辟空间if(nextval ==NULL){perror("malloc fail:");returnNULL;}nextval [0]=-1;inti =1;//当前下标intk =-1;//回退下标while(i<len){if(k==-1||str2[i -1]==str2[k]){//k+1防止越界，并且k+1为str2[i]的回退下标//回退字符与原字符相同if(str2[k +1]==str2[i]){nextval[i]=nextval[k+1];}else{nextval[i]=k +1;}k++;i++;}else//回退{k =nextval[k];}}returnnextval;}intKMP(Sstring*s1,Sstring*s2,intpos){assert(s1 &&s2);intlen1 =StrLength(s1);intlen2 =StrLength(s2);if(len1 ==0||len2 ==0){return-1;}if(pos <0&&pos >=len1){return-1;}int*nextval =GetNext(s2);inti =pos;intj =0;while(i <len1 &&j <len2){if(j ==-1||s1->data[i]==s2->data[j]){i++;j++;}else{j =nextval[j];//更新至next数组}}if(j >=len2){returni -j;}free(nextval);//释放内存return-1;}

    3.6. 复杂度分析

    我们用M表示文本串的长度，N表示模式串的长度。

    img

    1. 第一步都从字符串的起始位置开始匹配。我们只需让i下标减去j下标就会回到原来的起始位置，这是再加1就是我们下一次匹配的开始位置。
    2. 前缀：指从串首开始到某个位置i结束的一个特殊子串。

      • 时间复杂度：文本串并不回退，时间复杂度为O(M)，模式串时间复杂度也可以近似看做O(N)，即使在最坏情况下，KMP 算法的时间复杂度为 O(mn)，但这种情况很少发生，通常情况下，KMP 算法的时间复杂度是线性的，可以在很短的时间内完成字符串匹配。结果判定

        1. 不断重复上述步骤。

      3. img

      • **情况二：当s2[k]!=s2[j]时，这时我们需要重新匹配最长公共真前后缀。Brute- Force算法在模式串中有多个字符和文本串中的若干个连续字符比较都相等,但最后一个字符比较不相等时,文本串的比较位置需要回退。

      而KMP 方法算法就利用之前判断过的信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度(最长公共真前后缀)，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。

      img

      • 起始位置1与i下标之间的元素个数就是j下标与起始位置2之间的个数。
      • 进行循环遍历更新：
    • 若 k == -1或者模式串中 str2[i - 1] == str2[k]，则 next[i] = k + 1，并且使 i递增，k也递增。

      • img

      1. 问题三：为什么next数组求出的回退下标就能让文本串的下标不回退呢？

      我们可以先看看这幅图

      img

      当文本串s1与模式串s2出现不匹配的情况时前面的字符是匹配成功的。

      假设我们有两个字符串，分别记为s1与s2。

      • 时间复杂度：BF算法最理想的时间复杂度是O(N)，即在文本串的最开始位置就找到。

      三、 而求next数组我们分为以下几步：

      1. 首先第一步求模式串的最长公共真前后缀(前缀以下标0开始，后缀以j-1结束)，记作s2[0,p1]=s2[p2,j-1]，其中p1-0=j-1-p2=>p2=j-1-p1。
      2. 然后就可以推出新的最长后缀是以j下标结尾长度不超过k的子串，该子串又可以分为s2[j-k，j-1]中以j-1下标结尾长度不超过k-1的最长后缀(长度设为k1)+s2[j]。当i移动到末尾时，匹配失败返回-1。
      3. 将 next[0]初始化为 -1。
      4. 空间复杂度：BF算法并不需要格外的空间消耗，所以空间复杂度为O(1)。

        3.3. 求next数组

        KMP算法的精髓就在于next数组，记作next[j]=k，其中j是我们的移动下标，而k既是我们的回退下标，也是最长公共真前后缀的长度。并且设next[j]=k，那么问题就是求next[j+1]=？，这时我们可以分为两种情况讨论：

        • **情况一：**当s2[k]==s2[j]时，因为next[j]=k，所以s2[0,k-1]=s2[j-k,j-1]，最长公共真前后缀为k。这就导致一个问题，如果模式串过长出现这种情况，也会造成大量的时间销毁。所以就会出现一直回退的现象，因此引出了我们的优化nextval数组。