首页 > 其他分享 >字符串相关

字符串相关

时间:2023-08-06 20:22:05浏览次数:45  
标签:le 后缀 fail 字符串 相关 border operatorname 回文

KMP

下标从 \(1\) 开始求 border:

int kmp[N];
void KMP(char *s,int len){
	for(int i=2,j=0;i<=len;i++){
		while(j&&s[i]!=s[j+1])j=kmp[j];
		if(s[i]==s[j+1])j++;
		kmp[i]=j;
	}
}
int len;char s[N];
int main(){
	scanf("%s",s+1),len=strlen(s+1);
	KMP(s,len);
	for(int i=1;i<=len;i++)
		printf("%d ",kmp[i]);
	
    return 0;
}

Z 函数

可以 \(O(n)\) 求出一个字符串的所有后缀与另一个串的 LCP 长度。

  • 字符串 \(a\) 的 Z 函数数组 \(\{z\}\) 是 \(a\) 与其每一个后缀的 LCP 长度。

记 \(n=|S|\).

怎么 \(O(n)\) 地求出 \(S\) 的 Z 函数?

约定 \(z_0=0\),显然有 \(z_1=n\),考虑用 \(z_{1\sim i-1}\) 求出 \(z_i\).

记 “\(l\) 处的匹配段” 为 \(s[l:]\) 与 \(S\) 的 LCP \([l,l+z_l-1]\),目前右端点最大的匹配段为 \([l,r]\).

计算 \(z_i\) 时显然有 \(l<i\)。若 \(r<i\),初始化 \(z_i=0\) 并暴力扩展。

否则由 \(S[1:r-l+1]=S[l:r]\),可以利用 \(z_{i-l+1}\) 的值,初始化 \(z_i=\min\{r-i+1,z_{i-l+1}\}\),暴力扩展 \(z_i\).

匹配过程中 \(r\) 不降,时间复杂度 \(O(n)\).

void Z(char *s,int n){
	z[1]=n;
	for(int i=2,l=0,r=0;i<=n;i++){
		if(i<=r)z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])z[i]++;
		if(i+z[i]-1>r)l=i,r=i+z[i]-1;
	}
}

P5410 【模板】扩展 KMP(Z 函数)

试求出

  • \(b\) 的 Z 函数 \(\{z\}\).

  • \(b\) 与所有 \(a[i:]\) 的 LCP \(\{p\}\).

\(|a|,|b|\le 2\times 10^7\).

后者与求 Z 函数的过程基本一致。

时间复杂度 \(O(|a|+|b|)\).

void exKMP(char *s,int n,char *t,int m){
	Z(t,m);
	for(int i=1,l=0,r=0;i<=n;i++){
		if(i<=r)p[i]=min(z[i-l+1],r-i+1);
		while(i+p[i]<=n&&s[i+p[i]]==t[p[i]+1])p[i]++;
		if(i+p[i]-1>r)l=i,r=i+p[i]-1;
	}
}

P2375 [NOI2014] 动物园

记 \(\operatorname{num}(T)\) 为其长度 \(\le\lfloor\frac{|T|}{2}\rfloor\) 的 border 数。

对 \(i=1\sim n\) 求出 \(\operatorname{num}(S[:i]).\)

\(T\le 5\),\(n\le 10^6\).

跑 KMP 并建立 fail 树,那么 \(\operatorname{num}(S[:i])\) 即 \(i\) 的 \(\le \lfloor\frac{i}{2}\rfloor\) 的祖先数目。

一遍 dfs 即可,用栈记录跟到当前点的路径。

时间复杂度 \(O(Tn\log n)\).

record


P5829 【模板】失配树

多次询问 \(S[:p]\) 和 \(S[:q]\) 的最长公共 border 长度。

\(n\le 10^6\),\(m\le 10^5\).

border 集合显然等价与 fail 树上的祖先集合。

求出 \(lca_{p,q}\) 的即可。特别地,\(lca\) 不能为 \(p,q\) 本身,此时往上爬一层就好。

record


P3426 [POI2005] SZA-Template

这里要提出一个 “覆盖” 的定义:

若 \(T\) 再 \(S\) 中的出现区间的并集为 \([1.|S|]\),则称 \(T\) 覆盖 \(S\).

试求出覆盖 \(S\) 的最短串的长度。

\(n\le 5\times 10^5\).

所求串一定是 border,枚举其长度 \(i\).

对于每个出现的结束位置 \(j\),显然有 \(S[:i]\) 是 \(S[:j]\) 的 border,故 \(j\) 在 \(\operatorname{Subtree}(i)\) 中。

那么合法当且仅当对 \(\operatorname{Subtree}(i)\) 排序,其最大 \(\rm gap\le i\).

具体用双向链表实现。每次将非 border 路径的子树信息全部删去,然后得到 gap.

record


Fedya the Potter Strikes Back

*3200,比较困难。


P5466 [PKUSC2018] 神仙的游戏

串包含 \(0,1\) 和通配符,问 \(s\) 可能存在的 border 长度集合。

\(|s|\le 5\times 10^5\).

如果有长为 \(d\) 的 border 那么就有长为 \(n-d\) 的周期。

对于 \(i\equiv j\space(\operatorname{mod} x)\),显然 \(s_i\) 和 \(s_j\) 不能互为 \(0\) 和 \(1\).

对于 \(s_i=0\) 赋值 \(F_i=1\),\(s_i=1\) 赋值 \(G_{n-i}=1\).

把他们卷起来可以口胡到一个比较正确的结论,大概就是减去 \(n\) 然后取绝对值,对于 \(d\) 枚举其所有倍数就好了。

record


关于周期和匹配

Weak Periodicity Lemma

  • 若 \(p,q\) 为 \(S\) 的周期,且 \(p+q\le n\),则 \(\gcd(p,q)\) 也是 \(S\) 的周期。

不妨设 \(p>q\),\(d=p-q\).

当 \(i>q\) 时,有 \(s_i=s_{i-q}=s_{i-q+p}=s_{i+d}\).

当 \(i<p\) 时,有 \(s_i=s_{i+p}=s_{i+p-q}=s_{i+d}\).

故 \(d\) 是 \(s\) 的周期,辗转相减即可。


Periodicity Lemma

  • \(p+q-\gcd(p,q)\le n\Longrightarrow\gcd(p,q)\) 是 \(S\) 的周期。

约数周期定理

  • 若 \(S=T[:i]\),\(T\) 有周期 \(a\),\(S\) 有周期 \(b\),\(b|a\),\(|S|\ge a\),那么 \(T\) 有周期 \(b\).

显然成立。


  • \(S\) 的长度 \(\ge |S|/2\) 的 border 长度构成一个等差序列。

它等价于 “\(S\) 的长度 \(\le |S|/2\) 的周期构成一个等差序列”。

记最小周期为 \(p\),另一个 \(\le |S|/2\) 的周期为 \(q\)。由 WPL 得 \(\gcd(p,q)\) 是 \(S\) 的周期,则必有 \(p|q\),等差周期的存在性显然。


  • \(S\) 的 border 长度可划分为至多 \(\lceil\log_2|S|\rceil\) 的等差序列。

去除 \(\ge|S|/2\) 的 border 长度,容易发现其实进入了子问题,每次规模减半。


等差匹配定理

  • 若 \(2|S|\ge|T|\),则 \(S\) 在 \(T\) 中的匹配位置为等差序列。

将 \(T\) 中没有被匹配覆盖的部分去掉,使得 \(T\) 被 \(S\) 覆盖。

显然匹配次数 \(\le 2\) 时为等差数列。现在对匹配次数 \(\ge3\) 的情况讨论。

设第一、二次匹配间隔为 \(d\),之后某次匹配与第二次间隔为 \(q\),把这三次匹配分别记作 \(S_1,S_2,S_x\).

容易发现 \(d,q\) 是 \(S\) 的周期。

由 \(2|S|\ge|T|\),\(d+q+|S|\le|T|\) 有 \(d+q\le |S|\).

设 \(S\) 的最小周期为 \(p_{min}\),显然 \(p_{min}\le d,q\),\(p_{min}|d\).

于是 \(S_1\cup S_2\) 有周期 \(p_{min}\),若 \(p_{min}<d\),则存在 \(S_2\) 左移后的另一个匹配,矛盾。故 \(p_{min}=d\).

由 WPL 得 \(r=\gcd(d,q)\) 是 \(S\) 的周期,故 \(d|q\).

于是不存在非等差的匹配。


P5287 [HNOI2019] JOJO

这个显然也是十分困难的。


[ARC060F] 最良表現

若一个串不是整循环串,称之为好串。

求出 \(S\) 的好串拆分的最小段数以及满足最小前提的方案数。

\(|S|\le 5\times 10^5\).

两种特殊情况:

  • \(S\) 中只有一种字符,只能拆分为 \(|S|\) 段。

  • \(S\) 本身为好串。

接下来考虑 \(S\) 为整循环串的情况。可以发现最小段数一定是 \(2\).

这个东西有证明,但是看起来十分显然,因为 \(S[:|S|-1],S[|S|]\) 就是一种合法方案。

接下来枚举各种切分判定是否合法。

也就是对每个前后缀判定是否为整循环串。

Lemma

  • 整循环的最小循环节必然是最小整循环节。

用 kmp 求出它们的最小循环节。

record


[ARC077F] SS

好像是很经典的困难题。不知道是不是。


P4156 [WC2016] 论战捆竹竿

需要使用同余最短路的技巧。


回文

  • 记 \(S_R\) 为 \(S\) 翻转后的串。

  • 若 \(S=S_R\),则 称 \(S\) 为回文串。

回文自动机(PAM)

结构

PAM 的每个节点表示原串的一个(本质不同的)回文子串。

转移边表示给当前串左右同时加上某个字符。这样偶回文串只能到达偶回文串,奇回文串同理,故有一奇一偶两根。

奇根指向单字符字符串,为方便约定奇根的 \(len\) 为 \(-1\).

\(\operatorname{fail}\) 边指向自己的最长回文后缀。约定偶根的 \(\operatorname{fail}\) 指向奇根。

从结尾在原串末尾的最长回文子串向上跳 \(\operatorname{fail}\) 得到的链称为终止链。它表示了原串的所有回文后缀。

构造

增量法,每次向串末尾添加一个字符 \(x\),考虑加入 \(x\) 后的新回文后缀。

Lemma

  • 每添加一个字符,至多新增一个新的本质不同的回文串,且是所有回文后缀中最长的。

附一张yyc学长放的图就好了。

推论:本质不同的回文子串(也就是 PAM 的节点数)的上界是 \(|S|\).

考虑如何找到这个最长的新回文后缀。对于每个新回文后缀,去掉其两侧的 \(x\) 后一定对应一个旧回文后缀。

暴力跳旧终止链,检查对应回文串左侧是否有一个 \(x\)。由于终止链上长度随深度递增,跳到了符合要求的点 \(v\) 时,就找到了最长的新回文后缀。

维护转移边。若 \(v\) 有 \(x\) 出边,则该最长回文后缀已经在前面出现过,找出 \(v\xrightarrow{x}d\),令终止链末尾为 \(d\).

否则,新建点 \(u\) 储存该后缀,连 \(v\xrightarrow{x}u\),且 \(\operatorname{len}(u)=\operatorname{len}(v)+2\).

维护 \(\operatorname{fail}\) 边。顺着终止链找下一个旧的回文后缀 \(v'\) 满足左边有一个 \(x\).

新次长回文后缀一定出现过,故 \(v'\) 有 \(\xrightarrow{x}\) 出边,找出 \(v'\xrightarrow{x}u'\),则 \(\operatorname{fail}(u)=u'\).

若找不到 \(v'\),将 \(\operatorname{fail}(u)\) 置为偶根。

复杂度证明

求 \(\operatorname{fail}\) 之外的复杂度显然为 \(O(n)\).

\(\operatorname{fail}\) 指向其回文真后缀,长度单调不增,同一深度最多跳 \(2\) 遍 \(\operatorname{fail}\)(奇根、偶根所在树),而新建节点时深度只会加 \(1\),所以跳 \(\operatorname{fail}\) 的上界为 \(2n\).

时间复杂度 \(O(n)\),空间复杂度 \(O(n|\Sigma|)\).

struct Palindrome_Automaton{
	int ch[N][S],fail[N],len[N],cnt,last;
	void init(){
		cnt=fail[0]=fail[1]=1;
		len[1]=-1;
	}
	int getfail(int x,int i){
		while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
		return x;
	}
	void insert(char c,int i){
		int x=getfail(last,i),w=c-'a';
		if(!ch[x][w]){
			len[++cnt]=len[x]+2;
			int tp=getfail(fail[x],i);
			fail[cnt]=ch[tp][w];
			ch[x][w]=cnt;
		}
		last=ch[x][w];
	}
}PAM;

经典应用

  • 求本质不同回文串数

  • 求在各个位置结尾的回文串数

  • 求公共回文串数


P5496 【模板】回文自动机(PAM)

对于每个 \(i\) 求出 \(S[:i]\) 的回文后缀个数。强制在线。

\(|S|\le 5\times10^5\).

只需要记录 PAM 上当前节点的深度即可。

record


Palindromic characteristics

所有串都是 \(0\) 阶回文串。

对 \(k\ge1\),若 \(S\) 是回文串,且 \(S[1:\lfloor|S|/2\rfloor]\) 是 \(k-1\) 阶回文串,则称为 \(k\) 阶回文串。

对于 \(k= 1\sim |S|\) 求 \(S\) 的 \(k\) 阶回文子串个数。

\(|S|\le 5000\).

容易想到直接上 dp。记 \(f_{i,j}\) 为 \(s[i:j]\) 的回文阶数。

若 \(s_i\not=s_j\) 或 \(f_{i+1,j-1}=0\),\(f_{i,j}=0\).

否则 \(f_{i,j}=f_{i,i+\frac{j-i+1}{2}-1}+1\).

record

加强

这里讨论yyc放的 \(5\times 10^6\) 怎么做。

建立 PAM,记节点 \(u\) 长度 \(\le \operatorname{len}(u)/2\) 的最长回文后缀为 \(\operatorname{half}(u)\).

记新产生的点为 \(np\) 且有 \(p\xrightarrow{x}np\),那么先找到 \(\operatorname{half}(p)\),然后向祖先跳直到能产生对应回文后缀为止,出边指向的点即 \(\operatorname{half}(u)\),复杂度证明类似。

记 \(f_u\) 为回文串 \(u\) 的阶数,有

\[f_u=\begin{cases}f_{\operatorname{half}(u)}+1&(\operatorname{len}(\operatorname{half}(u))=\lfloor\operatorname{len}(u)/2\rfloor)\\1&\text{otherwise.}\end{cases} \]

求出每个回文串的阶数,乘以出现次数并求和即可得到答案数组。


P4762 [CERC2014] Virus synthesis

初始有一个空串,可以

  • 在串的左边或右边加一个字符

  • 在串的左边或右边加上其逆串

问构造 \(S\) 的最小操作数。

\(|S|\le 10^5\),\(\Sigma=\{A,T,C,G\}\).

考虑求出 \(f_i\) 表示转移的节点 \(i\) 的回文串的最小操作数。

我们希望尽量使用操作2,最终答案应为 \(\min\{f_i+n-\operatorname{len}(i)\}\).

跟前文一样,可以先找到 \(\operatorname{half}(u)\),剩下的暴力填一半,接着做一次操作2,也就是

\[f_u=f_{\operatorname{half}(u)}+\operatorname{len}(u)/2-\operatorname{len}(\operatorname{half}(u))+1 \]

具体实现就是额外掏一个东西出来再跳几遍。

虽然多测但是 \(\rm 1s\sim 10s\) 的时限确实没看懂。

record


可持久化 PAM

记 \(u.tr[c]\) 为 \(\operatorname{ancestor}(u)\) 中第一个左侧有 \(c\) 的节点。

维护时若 \(u\) 是 \(v\) 的祖先,则 \(v\) 继承 \(u.tr\),并将自己左侧字符对应的 \(tr\) 修改。

暴力跳终止链的复杂度是 \(O(n|\Sigma|)\),可以优化到 \(O(n\log|\Sigma|)\).


双端 PAM

维护 \(\operatorname{fail'}\) 表示最长回文前缀,它总和 \(\operatorname{fail}\) 相同,实际上不需要额外维护。

只需要记下正反两条终止链的末端就可以实现两侧插入。

当整个串变为回文串时要更新另一侧的终止链末端。


回文与 Border

  • 若回文串 \(S\) 有周期 \(p\),则一个循环节可以被拆成两个回文串,长度分别为 \(p-(|s|\operatorname{mod}p)\) 和 \(|s|\operatorname{mod}p\).

附上yyc放的图。

记 \(n=|s|\),循环节 \(t=s[:p]\),记 \(s=t^kt_1\),\(t=t_1t_2\).

那么有 \(t_R=t_2t_1\),\(t_R=t_{2_R}t_{1_{R}}\),那么 \(t_1,t_2\) 均为回文串,长度如上。

  • 设 \(v\) 为回文串 \(u\) 的最长严格回文前(后)缀,若 \(2|v|\ge|u|\),那么 \(v\) 只会在 \(u\) 中恰好匹配两次,作为前缀和后缀。

取出前两次匹配 \(v_1,v_2\),假设还有第三次匹配。

结合 Border 论,\(2|v|\ge|u|\Rightarrow v\) 在 \(u\) 的匹配位置成一个等差序列,公差为 \(v\) 的周期。

那么可将 \(v\) 的循环节写为两个回文串 \(p_1,p_2\),记 \(v=(p_1p_2)^kp_1\).

那么 \(v_1\cup v_2=(p_1p_2)^{2k}p_1\) 是一个更长的回文前缀。矛盾。


最小回文划分

过于难的东西还是不记了。


最小后缀

概念

记 \(\operatorname{suf}(S)\) 为 \(S\) 的后缀集合。

记 \(\operatorname{minsuf}(S)\) 为 \(S\) 的最小后缀。

记 \(\operatorname{Ssuf(S)}=\{V\in\operatorname{suf}(S)|T,VT=\operatorname{minsuf}(ST)\}\),即在 \(S\) 后面加上一个串后可能成为最小后缀的后缀,或 \(\rm Significant\space Suffixes\).


性质

  • \(\forall U,V\in\operatorname{Ssuf}(S)\),\(|U|<|V|\Rightarrow U\) 是 \(V\) 的前缀。

若 \(U\) 非 \(V\) 的前缀,对于任意 \(T\) 都有 \(UT<VT\).

又因为 \(U\) 是 \(V\) 的后缀,所以 \(U\) 是 \(V\) 的 border.

倍长定理

  • 若 \(S\) 有两个 \(\operatorname{Ssuf}U,V\) 满足 \(|U|<|V|\),则 \(2|U|<|V|\).

反证,假设 \(|U|<|V|<2|U|\).

由上面有 \(U\) 是 \(V\) 的 border,即对应长度为 \(|V|-|U|<|U|,|V|/2\) 的周期。

记一个周期为 \(T\),且有 \(U=T^kC,V=T^{k+1}C\).

由 \(\operatorname{minSuf}\),存在 \(R\)(可空)使得 \(UR<VR\).

\[\Longrightarrow T^kCR<T^{k+1}C\Longrightarrow CR<TCR \]

\[\Longrightarrow CR<UR \]

\(CR\) 也是后缀,那么 \(UR\) 必定不为最小后缀,矛盾。

这里没看太懂为什么当前钦定了 \(U\) 为 \(\operatorname{minSuf}\).

推论:\(|\operatorname{Ssuf}(S)|=O(\log|S|)\).

差不多写完了。后面太难了。

标签:le,后缀,fail,字符串,相关,border,operatorname,回文
From: https://www.cnblogs.com/SError0819/p/17609933.html

相关文章

  • 请输入一个字符串 由此可以得出这个字符串大写字母.小写字母.数字.符号的个数
    importjava.util.Scanner;publicclassDemo02{  publicstaticvoidmain(String[]args){    System.out.println("请输入一个字符串:");    Stringcc=newScanner(System.in).nextLine();    char[]arr=cc.toCharArray();    intc......
  • 【JavaScript08】字符串基本操作
    字符串基本方法,本文只对部分方法做了说明其它更多参考菜鸟教程https://www.runoob.com/jsref/jsref-obj-string.htmls.split()字符串切割s.substr(start,len)字符串切割,从start开始切,切len个字符;如果len不给,直接切到最后s.substring(start,end)字符串切割,从st......
  • 【JavaScript09】模板字符串(Template Strings)
    前言JavaScript在ES6新增了模板字符串(TemplateStrings)语法,其作用是可以在字符串中换行,以及将变量和表达式插入字符串。模板字符串模板字面量使用反引号(``)而不是单引号('')或双引号("")来定义字符串示例:letuser="xwl";letage=20;letx=`myname......
  • zabbix触发器标签提取监控项子字符串功能实现对应告警恢复
    0实验环境zabbix6.01监控项1.1监控项设置通过zabbixagent自定义监控项,读取某文件内容模拟日志/trap告警,测试获取触发器标签中提取子字符串功能,以及相同标签的触发器自动恢复功能。1.2手工运行手动触发之后,模拟产生如下日志数据,意为集群中node-01主机离线。07:28:29......
  • 代码随想录算法训练营第七天|力扣334.反转字符串、力扣541.反转字符串II、剑指offer05
    字符串反转字符串(力扣344.)如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。毕竟面试官一定不是考察你对库函数的熟悉程度,如果使用python和java的同学更需要注意这一点,因为python、java提供的库函数十分丰富。如果库函数仅仅是解题过程中的一小部分,并且......
  • 前端学习笔记202306学习笔记第三十八天-Es6-字符串的解构赋值1
      ......
  • 【ACM专项练习#02】输入整行字符串、输入值到vector、取输入整数的每一位
    输入整行字符串平均绩点题目描述每门课的成绩分为A、B、C、D、F五个等级,为了计算平均绩点,规定A、B、C、D、F分别代表4分、3分、2分、1分、0分。输入有多组测试样例。每组输入数据占一行,由一个或多个大写字母组成,字母之间由空格分隔。输出每组输出结果占一行。如果输入的大......
  • 11_字符串操作函数
    字符串操作函数以str开头的函数都是字符串操作函数都是遇到'\0'结束操作strlen测量字符串长度#include<string.h>size_tstrlen(constchar*s);s:需要测量字符串的首元素地址charstr[128]="hello";strlen(str);//5strcpy字符串拷贝函数#include<string.h>......
  • nginx离线安装配置,项目部署相关配置,https ssl配置
    一、nginx安装1。通过nginx.org下载源码安装包,或直接wget下载点击链接去下载选择对应系统版本即可。我这里从稳定版【Stableversion】下载2.安装nginx依赖环境包yuminstallgcc-c++pcrepcre-develzlibzlib-developensslopenssl-devel3.上传或者下载nginx安装......
  • 浅谈非栈上格式化字符串
    浅谈非栈上格式化字符串这里先浅分析修改返回地址的两种打法,分别是"诸葛连弩"和”四马分肥“修改返回地址本文例题以陕西省赛easy_printf为主简单看一看程序需要先过一个判断然后进入vuln进入后有一个13次的循环可以让我们操作第一步肯定要先leak出栈地址程序......