做题记录 25.9.23

szt100309 · 2025-09-23 15:01:03 · 个人记录

\purple\odot P10716 【MX-X1-T4】「KDOI-05」简单的字符串问题

特判 k=1 的情况

一个 A 合法当且仅当 A 是 S[1:i] 的 \text{border} 且 A 在 S[1:i] 中不重叠出现了至少 k 次

建立 \text{fail} 树，则合法的 A 一定为树上一个点到根的链上全体点，设是 u 到根的链上全体点

显然 u 为 i 的祖先，且 u 为 i 的祖先中第一个满足 S[1:u] 第 k 次出现的结束位置 \le u 的

令 p_{u,k} 表示 S[1:u] 在 S 中第 k 次不重叠出现位置的右端点，显然 k=O(\frac nu)，直接存储可以接受

假定已经预处理 p，容易树上倍增 O(\log n) 求出一次询问的答案

考虑如何计算 p

先计算出 z 函数，枚举 i=1\sim n，初始将 i 加入 p_i，然后暴力向后跳，最后删去所有 z_\ast=i 的位置，用并查集维护下一个可行位置，即可做到 O(n\alpha(n)\ln n)

总时间复杂度 O((n\alpha(n)+q)\log n)

代码

参考

考虑算出 a_i=\sum_{l\le \frac i2}[s[i-2l+1,i-l]=s[i-l+1,i]]，b_i=\sum_{l\le \frac{n-i+1}2}[s[i,i+l-1]=s[i+l,i+2l-1]]，则答案为 \sum_i a_i b_{i+1}

两者计算方式类似，以 a 为例

枚举 l，考虑 l,2l,3l,\cdots 这些位置，显然每组 s[i-2l+1,i-l] 和 s[i-l+1,i] 恰好分别穿过相邻的一对位置，枚举 x=(c-1)l 和 y=cl，考虑分别穿过两者的组的贡献

令 pl=\text{lcs}(s[1:x],s[1:y])-1,sl=\text{lcp}(s[x:n],s[y:n])-1，则会令 a_{y-pl+l-1\sim y+sl} 加一

差分维护即可

时间复杂度 O(\sum n\log n)

代码

参考