数据结构-第四章

字数统计: 367字   |   阅读时长≈ 1分

数据结构

第四章 串

author:slightwjq
2021年8月11日

定义和实现

0-n个字符组成的有限序列。
C语言中存在‘堆’区域，用malloc()分配和free()释放存储空间。

模式匹配

简单的模式匹配

就是一种暴力求解的方式进行的循环算法，在很多情况下时间复杂度较高。
最坏时间复杂度O(mn)，不再赘述。

KMP算法

KMP是一种改进的模式匹配算法，主要优化在于主串的指针无需回溯，模式串的指针回溯一部分。平均时间复杂度为O(m+n)。
模式匹配算符复杂度高因为需要不停地回溯，而KMP有效的减轻了这个问题。
KMP算法中：右移位数 = 已匹配的字符数 - 对应部分的匹配值
用公式描述为：Move = (j-1) - next[j]
next[j]的含义是：在子串的第j个字符与主串匹配失败时，跳到子串的next[j]位置重新与主串当前为主串当前位置进行比较。
next[1] = 0; next[2] = 1; else next[j] = 1+ (1 ~ j-1的最长相等前后缀长度)。

KMP算法的优化

通过剪枝？的思想对KMP的next数组进行优化。
新的nextval通过next得到。
若 j 位置的字符与 next[j] 位置的字符一致，则next[j] = next[next[j]]
即要跳转的位置的值设置为该位置的next值。

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

还在学习中的在读硕士，网站可能有些连接暂无法正常使用，有问题可以联系QQ:2863826649