字符串小结

KMP 复杂度的证明

咕咕

一道题

给一个串, 支持插入删除最后面的字符, 求循环节的长度。这里的循环节是整个串的循环节,任意一个都可以.

求循环节就相当于求 Next 指针,考虑 Next 指针的构建过程。当前的 Next 指针是建立在之前的 Next 指针的基础上的。当 Next 指针跳到一个可以匹配的位置时,也就构成了这次的 Next 指针。但是,对于上一次 Next 指针的转移状态是不方便记录的。那么为了方便,我们可以建立 KMP 自动机——即单串版本的 AC 自动机。

把问题中的操作离线一下,全部变成在后面加字符的操作。既然在末尾添加字符,那么就可以 的复杂度更新 AC 自动机;我们的目标即为,跳 fail 指针,直到跳到当前结点的祖先结点上,那么这时就是这个字符串的 border 啦

又一道题

模板串 为一个排列, 问 的多少子串能与模板串匹配,匹配的条件是,子串元素的相对大小关系与模板串相同。

这里的匹配与一般的字符串匹配不同,因此我们考虑针对这种匹配的 Next 指针的构造。

那么问题就变成怎么判断当前的 border 的最后一个字符是匹配的。如果匹配那么就求出了当前的 Next 指针,不匹配就跳。

判断很简单,因为我们知道,当前 border 除末尾字符外的字符都是匹配的,那么只需要

离散 next,主席树维护 next,双向链表,倒着删除,预处理排列的前驱后继

离散 KMP 匹配

扩展 KMP Z-algorithm

可以求两个后缀的 LCP

求 AA

分治,那么考虑跨过中线的 AA 串

正反两遍 ZA,统计贡献即可

求 AAA……的循环串也是差不多的思路,边界稍微讨论一下即可

AC 自动机

出现多次算一次

动态 AC 自动机,模式串可以读入

二进制分组(划分),插入字符串的时候,把末尾的 AC 自动机暴力重构

查询的时候在 log 个 AC 自动机上查询

关于重构:均摊复杂度是对的

manacher 与回文树

manacher 先咕着

双倍回文?(前后相同不同)

先 manacher 扫一遍,标记一下

枚举中间分隔的位置,尝试找最长回文后缀和最长回文前缀,可以线段树维护

相同

后缀数组

O(1)LCP(转化为 RMQ)

求本质不同的子串个数:后缀数组求 LCP,总数减掉两两 LCP 即可,不用容斥

本质不同的子串在 SA 中天然字典序~

求字符串中 ABA 的子串的个数,len(B)<=10

分段,求 LCP,LCS,凑答案即可

调和级数,复杂度 .

TRIE 求后缀数组(推广到树上,其实是把 的后缀做排序, 倍增)


  转载请注明: Sshwy's Blog 字符串小结

 上一篇
概率期望小结 概率期望小结
摘要 Tqy 奆奆给我们讲概率啦 概率与期望概率空间三元组 . 被称为概率空间: 样本空间 是一个非空集合 集合 的元素是 的子集, 是样本空间 $\Omeg
2019.02.13
下一篇 
KMP 算法 KMP 算法
摘要 用于字符串匹配,在 O(n) 复杂度内完成匹配。 算法思想对于朴素算法,当 即匹配失败时,是将整个 S 向后移动一位,复杂度 O(mn)。这种算法的缺点在于,移动一
2019.02.12
  目录