字符串小结

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求后缀数组(推广到树上,其实是把 的后缀做排序, 倍增)