字符串专题 #2
青山依旧在，几度夕阳红
Problem A. P14212 [ROI 2016 Day2] 二进制输入
考虑 dp。对单词的长度进行阈值分治。
-
长度 \(\le B\)
把这些串的正串、反串插到两棵 Trie 上，每次转移在 Trie 上暴力走即可，单次转移 \(O(B)\)。
-
长度 \(>B\)
只有 \(\frac L B\) 个这样的串。使用前缀时，求出 LCP，对一段区间 Chkmin；使用后缀时，求出 LCS，对一段区间求 min。不难看出其实只需要后缀 Chkmin 和后缀 min，分别用 \(O(1)-O(\sqrt{n})\) 和 \(O(\sqrt{n})-O(1)\) 的分块。
总复杂度 \(O(n\sqrt{n})\)。
Problem B. CF1535F String Distance
观察 1：\(f(s,t)=1337\) 当且仅当 \(s,t\) 排序后不相等。
由此将串划分为若干个组。
观察 2：若 \(s,t\) 在同一组内，则 \(f(s,t)\le 2\)，因为总能对两个整串排序。
所以只需计数 \(f(s,t)=1\) 的对数。
\(f(s,t)=1\)，假设要操作 \(s\)，那么需要满足存在一个 \([l,r]\)，使得 \(s[1:l-1]=t[1:l-1],s[r+1:m]=t[r+1]:m\) 且 \(t[l,r]\) 单调。
实际上只需考虑 \(t\) 的所有极长单调段。这要求 \(s\) 的一段前缀和后缀必须和 \(t\) 的相同，分别对应正反串 Trie 上两个区间，二维数点统计。
Problem C. CF1801G A task for substrings
多模式串，考虑 AC 自动机。
拆一下贡献，答案变为 终于 \([l,r]\) 内的 减去 始于 \([1,l-1]\) 终于 \([l,r]\) 的。
重点在后一部分。分别建出正反串的 ACAM，找出 \(s[1:l-1]\) 在正串 ACAM 上对应的节点 \(p\) 和 \({\rm rev}(s[l:r])\) 在反串 ACAM 上对应的节点 \(q\)。枚举 \(p\) 在失配树上的祖先以及经过 \(p\) 的所有串 \(t\)，判断 \(t\) 剩下的部分是否是 \(q\) 的祖先。
\(q\) 可以失配树上倍增找到，而贡献可以离线下来挂到 \(p\) 上，dfs 正串失配树，给反串失配树做子树加。这个枚举总数是 \(O(S)\) 的。
还有一个更简洁的做法。考虑找出最靠右的非法串 \(t\)，设其终于 \(p\)，那么终于 \([p+1,r]\) 的都合法。终于 \([l,p]\) 的合法串一定是 \(t\) 一个后缀的子串，所以只要求出一个模式串的一个后缀里有多少其他模式串即可，这个可以在反串 ACAM 上统计出来。