字符串复习与进阶

JSOI2007 字符加密

把字符串倍长，求后缀数组后把前一半后缀对应的位置按序输出即可。

即使字符串有循环节也是不要紧的。

代码

Luogu2870 Best Cow Line

如果首尾字符不同就可以直接选择；如果相同，我们就比较这个前缀和后缀的字典序大小。可以证明这样是最优的。

那么把这个串反过来在后面接上，然后中间插入一个分隔符，建立后缀数组即可。

代码

CF30 E Tricky and Clever Password

我们考虑枚举中间点，manacher 计算最长回文串，那么整个串就划分为了$A+B+C$，其中$B$是回文串。那么问题就转化为了$A$的前缀与$R(C)$的 LCP。$R(S)$表示 S 的反串。那么我们就把原串倒过来，求出每个前缀与反串前缀的匹配长度（KMP），然后做前缀 Max 即可。

时间复杂度$O(n)$。

代码

CF873 F Forbidden Indices

建立 SAM 后，把没有被禁止的点加 1 的贡献，然后 fail 树上做前缀和就可以统计答案了。

代码

CF547 E Mike and Friends

题意：有$n$个串$s_1,\cdots,s_i$。定义$f(i,j)$表示$s_i$在$s_j$里出现的次数。有$q$次询问，每次询问$l,r,k$，问$\sum_{i=l}^r f(k,i)$。

$n\le 2\times 10^5,q\le 5\times 10^5,\sum |s_i|\le 2\times 10^5$。

考虑建立广义 sam，在插入一个串的时候在经过的所有结点上打上这个串的标记，表示这些状态以及它们在 fail 树上的祖先状态是这个串的子串。

那么在 fail 树上向上合并后，我们就得到了每个状态是哪些串的子串。那么询问就可以处理了。

使用线段树维护标记，线段树合并。复杂度$O(|\Sigma|\sum |s_i|\log_2n+q\log_2n)$。

代码

NOI2018 你的名字

给出一个字符串$S$，每次询问$(T,l,r)$，问所有$T$的本质不同的子串中，不在$S[l,r]$中出现的子串有多少个。

$|S|\le 5\times 10^5,\sum |T|\le 10^6$。

第一部分

首先考虑$l=1,r=|S|$怎么做。

我们建立$T$的 SAM 来将相同的子串归到一个状态里。

记$l(i)$表示$T[1,i]$的后缀与$S$的子串匹配的最长长度。对于$T$的 SAM 中的状态$x$，记录$pos(x)$表示这个状态在$T$中结尾的位置（可能有多个位置，选择任意即可）。记$L(x)$表示$x$这个状态的长度（即$len(x)$）。

那么$l(pos(x))$得到就是$x$这个状态与$S$匹配的最长长度。那么这个状态中不与$S$匹配的部分就是$L(x)-\max(L(fail(x)),l(pos(x)))$。于是答案就是

$$\sum_x \max(L(x)-\max(L(fail(x)),l(pos(x))),0)$$

第二部分

接下来考虑$l,r$任意的情况。那么$l(i)$表示的就是$T[1,i]$的后缀与$S[l,r]$的子串匹配的最长长度。如果求出了$l(i)$那么我们就可以根据上面的式子求答案了。

我们考虑在$S$的 SAM 接受$T$的时候计算$l(i)$。具体地，记录一个$cur$表示当前与$S[l,r]$匹配的长度。每次我们尝试接受$T[i]$：

• 如果当前状态的后继状态$tr(x,T_i)$中存在与$T[i-cur,i]$匹配且包含于$S[l,r]$的状态，那么就接受$T_i$并转移到后继状态，让$cur$自増，且$l(i)\gets cur$。
• 否则我们让$cur$自减并再次检查是否存在匹配的状态。
• 如果$cur=L(fail(x))$那么就跳转到$fail(x)$状态。

如何判断当前状态的后继状态$tr(x,T_i)$中是否存在与$T[i-cur,i]$匹配且包含于$S[l,r]$的状态？对于每一个 SAM 上的状态$x$记录一个集合$Q(x)$表示$x$所代表的子串在$S$中出现的位置右端点的集合（即 Right 集合）。那么我们查询$Q(x)$中是否存在区间$[l+cur,r]$里的元素，就可以判断是否存在与$T[i-cur,i]$匹配且包含于$S[l,r]$的状态。

使用线段树维护$Q(x)$即可，合并的时候使用线段树合并即可。

时间复杂度$O(|S|(|\Sigma|+\log_2|S|)+\sum |T||\Sigma|)$。

代码