数据结构严薇敏——KMP算法之next数组代码实现

谁践踏了优雅 2022-05-18 05:46 144阅读 0赞

**KMP算法是在已知模式串的next函数值的基础上执行的，所以必须先求出模式串的next数组值。**

**具体原理可以参考视频讲解**：[https://www.bilibili.com/video/av21828275/?p=39][https_www.bilibili.com_video_av21828275_p_39]

### 实现代码如下： ###

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXSIZE 255
    
    typedef unsigned char SString[MAXSIZE + 1];   //0号用来存放串的长度
    
    void Get_Next(SString T,int *next)
    {
        int i = 1;    //初始化i表示后缀
        int j = 0;    //初始化j表示前缀
        next[1] = 0;
        while( i < T[0] )
        {
            if( j == 0 || T[i] == T[j])
            {
                ++i;
                ++j;
                next[i] = j;
            }
            else
                j = next[j];
        }
    }
    int main()
    {
        int i = 1;
        SString T = " abaabcac";
        T[0] = 8;                   //存放串长
        int next[8];
        printf("模式串：%s",T);
        Get_Next(T,next);
        printf("\nnext数组的值为：");
        for(i = 1; i <= 8; i++ )
          printf(" %d",next[i]);
        printf("\n");
        return 0;
    }

n

[https_www.bilibili.com_video_av21828275_p_39]: https://www.bilibili.com/video/av21828275/?p=39

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关评严蔚敏《数据结构》中的KMP算法

最近老被KMP 算法给烦着，几经思考加探索加画图加验证加分析，终于在我的努力下，发现了书中一个重大的问题，它里面的KMP函数是化简了的，也就是说书上的解释与函数是不完全对

╰+哭是因爲堅強的太久メ/ 2022年09月24日 00:22/ 0 赞/ 168 阅读

相关数据结构严薇敏——线性表的链式存储（C语言）

线性表的链式存储结构特点使用一组任意的存储单元存储线性表的数据元素（这组存储单元地址可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其前后的数据元素的逻辑关系，除

╰+哭是因爲堅強的太久メ/ 2022年05月18日 20:10/ 0 赞/ 180 阅读

相关数据结构严薇敏——KMP算法之next数组优化代码实现

前面实现的next数组依然还有缺陷，当模式串中失配元素很多相同的前缀，有一部分的比较是不需要的。例如下面这种情况可以明显看出： ![70][] 因为模式串中第1、2、3

￡神魔★判官ぃ/ 2022年05月18日 06:14/ 0 赞/ 169 阅读

相关数据结构严薇敏——KMP算法之next数组代码实现

KMP算法是在已知模式串的next函数值的基础上执行的，所以必须先求出模式串的next数组值。具体原理可以参考视频讲解：[https://www.bilibili.com/

谁践踏了优雅/ 2022年05月18日 05:46/ 0 赞/ 145 阅读

相关数据结构严薇敏——串的定义、操作（C语言）

串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构。以下采用的是堆分配存储结构：它的数据类型定义为： typedef struct {

柔情只为你懂/ 2022年05月18日 03:43/ 0 赞/ 177 阅读

相关数据结构严薇敏——队列的链式存储（C语言）

如果用户的应用程序中设有循环队列，必须设定一个最大队列长度，若无法估计队列的长度，则采用链队列。关于队列的描述请看前面的博客。链队列代码：它的数据结构定义为：

r囧r小猫/ 2022年05月18日 01:56/ 0 赞/ 137 阅读

相关数据结构严薇敏——循环队列的顺序存储（C语言）

循环队列和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放数据元素外，还需要定义两个指针分别指向队头和队尾。它的数据结构定义为： type

落日映苍穹つ/ 2022年05月18日 01:54/ 0 赞/ 143 阅读

相关数据结构严薇敏——队列的顺序存储（C语言）

和栈相反，队列是一种先进先出的线性表。只能在表的一端进行插入，另一端进行删除。（类似与我们排队买东西，先到先得）队列中，允许插入的一端叫做队尾，允许删除的一端叫队头。代

缺乏、安全感/ 2022年05月18日 01:52/ 0 赞/ 173 阅读

相关数据结构严薇敏——栈的链式存储（C语言）

栈的链式存储和线性表的链式存储很类似，区别只是线性表的操作比较自由，而栈只能限定在表尾进行插入和删除。可以借助线性表的头插法来理解栈。它的数据定义结构为： typ

梦里梦外;/ 2022年05月18日 00:35/ 0 赞/ 154 阅读

相关数据结构严薇敏——栈的顺序存储（C语言）

栈是限定只能在表尾进行插入和删除操作的线性表。栈的特点是后进先出。它的顺序数据结构定义为 typedef struct SQSTACK {

短命女/ 2022年05月18日 00:27/ 0 赞/ 134 阅读