P4555 [国家集训队] 最长双回文串
题意：给定字符串 \(s\)，找到他最长双回文串 \(t\) 的长度。双回文串定义为存在一个 \(i > 1\) 使得 \(t[1, i)\) 和 \(t[i, n]\) 都是回文串。\(\vert s\vert \le 10^5\)。
二分哈希求出所有回文中心的半径，设以 \(i\) 为中心的最长回文串为 \([l_i, r_i]\)。
我们发现当两个回文中心确定时，最长双回文串的长度唯一确定（左边界向左延伸一格必须先使右边界往里缩一格，否则左右两串出现重叠）。
枚举回文中心 \(i\)，找到一个最小的 \(j\) 使得 \(r_j \ge l_i - 1\)，显然可以树状数组维护，在 \(r_i\) 的位置加入 \(i\)。submission
P3546 [POI2012] PRE-Prefixuffix
题意：定义 \(s\) 和 \(t\) 是循环相同的，当且仅当 \(s\) 能够将一个后缀移到开头使得与 \(t\) 完全相同。
给出字符串 \(s\)，找到最大的 \(i \le \frac{n}{2}\) 使得前缀 \(pre_i\) 和后缀 \(suf_i\) 是循环相同的。
枚举 \(s\) 的 border \(i\)，再找 \(s[i + 1, n - i]\) 的最长不重叠 border，令 \(s_i = s[i + 1, n - i]\)，发现把 \(s_i\) 的 border 掐头去尾就是 \(s_{i + 1}\) 的 border。
反过来讲，有 \(B_{\max}(s_i) \le B_{\max}(s_{i + 1}) + 2\)，设 \(p = B_{\max}(s_i)\)，当 \(i \to i - 1\) 时，令 \(p \to p + 2\)，然后不断减 \(1\) 直到合法，势能分析可以得出是线性的。
更加巧妙的做法：把 \(s\) 重排成 \(s_1s_ns_2s_{n - 1} \cdots\)，那么两个 border 就是最靠前的两个相邻回文串（长度皆为偶数），和上题一样维护。
Minimal String Xoration
题意：给定一个长度为 \(2^n\) 的字符串 \(s\)，选出一个 \(k \in [0, 2^n)\) 使得满足 \(t_i = s_{i \oplus k}\) 的字符串 \(t\) 的字典序最小，输出 \(t\)。\(n \le 18\)。
\(f(k, i)\) 表示选了 \(k\) 得到字典序最小的 \(t\) 的 \(2^i\) 的前缀，显然有 \(f(k, i) = f(k, i - 1) + f(k \oplus 2^{i - 1}, i - 1)\)，+ 表示拼接。
类似后缀数组 \(O(n\log n)\) 构造，求出 \(f(k, i - 1)\) 和 \(f(k \oplus 2^{i - 1}, i - 1)\) 在 \(i - 1\) 时的排名就可以当做两位数排序。
时间复杂度 \(O(n^22^n)\)，基数排序可以省掉一个 \(n\)。submission
x-prime Substrings
题意：定义只有数字组成的字符串 \(s\) 是 x-prime 的当且仅当 \(\sum s_i = x\) 且不存在一个子串和是 \(x\) 的真因子（不是他本身）。
给定字符串 \(s\) 和正整数 \(x\)，求 \(s\) 至少要删掉多少字符才不存在一个子串是 x-prime 的。\(\vert s\vert\le 1000, x\le 20\)。
注意到 \(x\) 很小，满足 x-prime 的字符串应当也很少，称之为非法子串。
删多少字符才能不存在非法子串的这类问题很容易想到构造 ac 自动机，最坏情况下，所有非法串构成的字典树大小只有 \(S = 4853\)。
\(f(i, s)\) 表示前 \(i\) 个字符匹配到 ac 自动机的状态 s 时需要删多少个才合法，枚举 \(i\) 删不删，时间复杂度 \(O(\vert s\vert S)\)。submission
P7361 「JZOI-1」拜神
题意：给定字符串 \(s\)，\(q\) 次询问 \(s[l, r]\) 出现至少两次的最长子串长度。\(n \le 5\times 10^4, q\le 10^5\)。
考虑询问的本质，长度 \(L\) 合法等价于存在 \(i ,j \in [l, r - L + 1]\) 满足 \(\text{lcp}(suf_i, suf_j) \ge L\)，可以二分。
后缀排序求出 height 数组，\(h_i = \text{lcp}(suf_{sa_i}, suf_{sa_{i - 1}})\)，考虑 \(suf_{sa_i}\) 与 \(suf_{sa_{i - 1}}\) 连边，那么 \(L\) 合法就是加入所有 \(h \ge L\) 之后 \(i, j\) 在同一连通块。
维护 \(nxt_i\) 表示与 \(i\) 在同一连通块的大于 \(i\) 的最小后缀编号，这个东西可以并查集的启发式合并实现，每个连通块开个 set 维护所有编号。
那么长度 \(L\) 到底怎么判断呢？区间查询 \([l, r - L]\) 当中最小的 \(nxt_i\) 是否 \(\le r - L + 1\)，显然可以线段树。
你当然可以离线。也可以维护持久化线段树 \(T_i\) 表示加入所有 \(h \ge i\) 后 \(1 \sim n\) 的 \(nxt\) 值，时空复杂度皆为 \(O(n\log^2n)\)。submission
标签：suf,选做,vert,20240904,题意,le,字符串,回文 From： https://www.cnblogs.com/Luxinze/p/18397011