字符串乱做

SAM相关。已经摆了。

这里是一些别的字符串题。

P10716

$q$ 次询问 $(i,k)$，计数合法的非空字符串 $A$ 使得存在可空字符串 $B_1,\cdots ,B_{k-1}$ 满足 $S[1,i]=A{B}_{1}A\cdots A{B}_{k-1}A$。

合法的 $A$ 是前缀且在失配树上是 $i$ 的祖先，答案为最大的合法前缀 $S[1,u]$ 在失配树上的 $de{p}_u$。

枚举 $u$，向后找不重叠的出现位置，即后缀和整个串 lcp $\ge u$，即第一个 z 函数 $\ge u$ 的位置。枚举完 $u$ 之后就删去 $z_p=u$ 的位置，并查集维护下一个位置。复杂度 $O(n\log n)$。

P11150

给定长为 $n$ 的 $S$。$q$ 次询问 $T$，最小化 $S[1,i]+T+S[i+1,n]$，再最小化 $i$。

先在 $s$ 末尾加入极大字符。要找到 $(i,j)$ 使得 $s[1,i]+t[1,j-1]=s[1,i+j-1]$ 且 $t_j<s_{i+j}$。最小化第一个不同的位置 $i+j$，再最小化 $t$ 从 $j$ 开始的后缀加上 $s$ 从 $i+1$ 开始的后缀，再最小化 $s$ 中的位置 $i$。

先枚举 $j$，枚举 $s_{i+j}=c$ 且 $t_j<c$，可以用 SAM 做子串定位找到最小的 $i$ 使得 $s[i+1,i+j]=t[1,j-1]+c$。然后对于相等的 $i+j$，预处理 $t$ 的后缀排序即可比较 $t$ 的两个后缀的字典序大小。

要比较$i1+j1=i2+j2$ 的 $(i1,j1)$ 和 $(i2,j2)$ ，有 $j2>j1$。如果 $j2$ 开始的后缀不是 $j1$ 开始的后缀的前缀，就直接比较 $r{k}_{j1}$ 和 $r{k}_{j2}$。否则比较 $t[j1+m-j2+1,m]$ 和 $s[i2+1,i1]$，因为之前匹配，所以 $s[i2+1,i1]$ 是 $t$ 的前缀。如果从 $j1+m-j2+1$ 开始的后缀不是从 $1$ 开始的后缀的前缀，那比较 $r{k}_{j1+m-j2+1}$ 和 $r{k}_1$；否则两个串完全相等。

此时已经找到了最小的串，但是 $i$ 选取的位置可以往前。找到 $t$ 的最小循环节 $l$，二分将 $i$ 向前挪 $l\times mid$，且 $s[i-l\times mid+1,i-mid]=s[i-l\times (mid-1)+1,i]$。

Q9406

给定 $n$ 个字符串，计数无序 $(x,y,z)$ 满足 $x>yz$ 或 $x>zy$ 且。 $y>xz$ 或 $y>zx$ 且 $z>xy$ 或 $z>yx$。

判掉含相等的若干情况。

不妨设 $x>y,z$，且 $y+z\ge z+y$。即 $y$ 是 $x$ 的前缀，$r{k}_{x-y}<r{k}_z<r{k}_x$。

按 $uv\le vu$ 给每个串排序，即分成三段分类讨论每段的 lcp，将所有串加上终止的极小字符求后缀数组。预处理出所有 $(x,y)$，按排序后的顺序枚举 $y$，区间查询。