首页 > 其他分享 >笔记:KMP的复习

笔记:KMP的复习

时间:2023-08-01 17:44:07浏览次数:47  
标签:判断 前缀 相同 ne 笔记 KMP 字符串 复习

Record

一个重要的字符串算法,这是第三次复习。

通过总结我认为之所以某个算法总是忘记,是因为大脑始终没有认可这种算法的逻辑(也就是脑回路)。

本篇主要讲解从KMP的应用场景,再到算法知识,以及例题。

Main

现有两个字符串 \(A, B\),求出 \(A\) 在 \(B\) 中出现的次数。
范围:字符串长度均 \(\leq 1e6 + 10\)。

其实简单来说,KMP就是优化了双重循环,解决字符串的匹配问题。

所以个人总结一下,遇到字符串的题目,如果dp用不了就考虑哈希和KMP

数学上从特殊到一般,那么这里我们从暴力到优化。

以 \(A = abab , B = abababaaabb\) 为例,一般做法是双重循环,时间复杂度 \(O(n ^ 2)\)。

我们来看这个具体是怎么实现的。

每次枚举一个初始点,然后一位一位的判断是否相同。如果相同,就继续判断直到;如果不同,就退出并且选择下一个点作为初始点。

首先,如果说判断到第 \(k\) 位发现不对,不是彻底无法挽救的。如果说这个子串从 \(1 .. k - 1\) 的前缀和后缀都没有相同的,比如说这种 \(abcfd\),那么判断过的位也不用再判断了,因为往后移一位就都错开了,所以就一直往后推,判断起点是否相同,相同就开始一位一位继续判断。如果说是这种 \(abcabc\) 那就好办了,因为我们可以进行如下的操作。

abcabcbdde
abcabcd

这个时候再第七位发现有问题了,是不是全部跳过呢?当然不是。

abc|abcbdde
   |abcabcd

再从相同的前缀开始就可以了。只不过显然这个情况下还是匹配不了。

    for(int i = 1, j = 0; i <= m; i ++ )
    {
        while(j && b[i] != a[j + 1]) j = ne[j];
        if(b[i] == a[j + 1]) j ++ ;
        if(j == n)
        {
            cout << i - n << ' ';
            j = ne[j];
        }
    }

通过这样的思路,只需要每次遍历一遍母串,时间复杂度 \(O(n)\)。

在匹配之前,得要算一下子串中每一位对应的最长的前缀和后缀,记录下前缀的最后一位。

    for(int i = 2, j = 0; i <= n; i ++ )
    {
        while(j && a[i] != a[j + 1]) j = ne[j];
        if(a[i] == a[j + 1]) j ++ ;
        ne[i] = j;
    }

例题

周期

利用ne数组的性质,马上就可以得到一个字符串最长的相同前缀和后缀。观察发现,存在循环节的字符串观察可知:

  • 当第 \(i\) 位存在 \(i \mod{(i - ne_i)} = 0\),那么他的循环节一定是 \(i - ne_i + 1 ... i\),个数是 \(i / (i - ne_i)\)。

这个自己打打草稿就出来了,不多说了。

代码

标签:判断,前缀,相同,ne,笔记,KMP,字符串,复习
From: https://www.cnblogs.com/SanGarden/p/17598594.html

相关文章

  • RASP知识学习笔记
    RASPRASP(Runtimeapplicationself-protection)是一种内置或链接到应用程序环境中的安全技术,与应用程序融为一体,实时监测、阻断攻击,使程序自身拥有自我保护的能力。工作原理RASP技术是一种基于服务器的技术,一旦应用程序运行开始时就会激活。而且,所有RASP产品都包含一个运行时监......
  • 关于菜鸡学习RHEL8的一些小笔记--->LVM逻辑卷
    LVM基础概念:LVM()逻辑卷管理器,主要适用于对Linux环境下面磁盘分区的管理机制在真实的场景中,服务器使用的越久,所产生的数据量就会越来越大,导致硬盘本身空间越来越小;这里针对分区来看,如果想要扩大容量,就得重新挂载硬盘,然后去做数据迁移,这样就会直接导致业务停止运行;#这里分区的大小是在......
  • 【学习笔记】记忆化搜索
    记忆化搜索目录前置知识:概念:实现:oiwiki:记忆化搜索建议搭配食用。前置知识:深度优先搜索DFS概念:搜索通常通过递归来实现,但是递归过程中往往有很多结果被重复计算,因此降低了搜索的效率。因此记忆化搜索就是再递归的过程中记录已经遍历过的状态与结果,用到的时候再直接取出......
  • 最小割树 学习笔记
    问题描述给定一张图,求任意两点的最小割。要求跑\(n\)次最大流。做法暴力需要跑\(n^2\)次最大流,然而这样很浪费,因为求出\(u,v\)两点的最小割以后,我们还获得了至少一种最小割方案,可以通过这一方案获得更多信息。注意到假设通过最小割断开后,\(s,t\)所在集合分别为\(S,T......
  • 如何提交学习笔记到Github
    前提条件:已经注册好Github账号步骤:*登录Github账号后,点击“+”新建仓库,根据提示命名和初始化仓库*克隆仓库到本地`gitclone<仓库的URL>`*在仓库文件夹里修改和添加文件*提交变更 *`gitadd*` *`gitcommit-m"对变更的描述"`*推送到Github`gitpushoriginmain`......
  • 白日梦的Elasticsearch实战笔记,32个查询案例、15个聚合案例、7个查询优化技巧。
    目录一、导读二、福利:账号借用三、_searchapi搜索api3.1、什么是querystringsearch?3.2、什么是querydsl?3.3、干货!32个查询案例!四、聚合分析4.1、什么是聚合分析?4.2、干货!15个聚合分析案例五、7个查询优化技巧公众号、欢迎关注一、导读Hi!大家久等了!时隔10天,白日梦的Elasticsea......
  • 白日梦的Elasticsearch实战笔记,ES账号免费借用、32个查询案例、15个聚合案例、7个查询
    目录一、导读二、福利:账号借用三、_searchapi搜索api3.1、什么是querystringsearch?3.2、什么是querydsl?3.3、干货!32个查询案例!四、聚合分析4.1、什么是聚合分析?4.2、干货!15个聚合分析案例五、7个查询优化技巧欢迎关注一、导读Hi!大家久等了!时隔10天,白日梦的Elasticsearch笔记......
  • C++ Primer 学习笔记——第九章
    第9章顺序容器前言本章是对第三章——字符串、向量和数组的扩展延伸,在第三章我们对标准库的顺序容器有一定了解,那么学习完本章我们对顺序容器的知识将会更加完整。标准库定义了几种关联容器,关联容器中元素的位置由元素相关联的关键字值决定。我们将在本章对关联容器做一定了解......
  • git学习笔记(十二):标签管理
    打标签,方便找。tag就是一个让人容易记住的有意义的名字,跟某个commit捆绑在一起。(就是一个指向commit的指针,原来的哈希表值太复杂了,不方便沟通,所以给了一种定制的简化版。)打标签切换到需要打标签的分支上,然后使用命令$gittagv1.0可以使用gittag查看所有标签。默认的标......
  • PyTorch基础知识-新手笔记
    逐元素操作Tensor中也有逐元素操作,大部分的数学运算都属于逐元素操作,逐元素操作的输入与输出的形状相同。常见的逐元素操作可参考下表:abs/add:绝对值/加法addcdiv(t,t1,t2,value=1):t1与t2按元素除后,乘以value加t,即t+(t1/t2)*valueaddcmul(t,t1,t2,value=1):t1与t2按元素乘后,乘......