BZOJ 3796 Mushroom追妹纸 题解

Statement

给 \(s_1,s_2,s_3\)，求最长的 \(w\) 的长度，满足

• \(w\) 是 \(s_1\) 子串
• \(w\) 是 \(s_2\) 子串
• \(s_3\) 不是 \(w\) 子串

Solution 1

以下是我没看题解瞎胡的

首先一个弱智想法是，枚举 \(s_1\) 上 \(w\) 的左端点，二分右端点，判定时 \(s_2\) 用 SAM，\(s_3\) 用单串 AC 自动机 / KMP。虽然复杂度不对，但是加点乱搞就能过。

然后优化，考虑在 \(s_1\) 上双指针，如何 \(O(1)\) 判定加入一个点时 \(s_3\) 是不是 \(w\) 子串？用 height 那一套求反串 lcp 即可。

Solution 2

以下是我看别的做法，转述的，不保熟

首先若没有 \(s_3\)，这是经典的“多串求最长公共子串”问题，有这样两种做法：

• 二分答案 \(x\)，因为 \(\min_{l\le i\le r}\text{height}(i)\le x\)，若一段极长满足 \(\text{height}(i)\le x\) 的 \(l,r\) 中同时出现 \(s_1,s_2\) 的后缀就可以。
• 因为 \(Ans=\max_{1\le l\le r\le \text{len}}\left\{\min_{p=l+1}^r\{|\text{lcp}(p,p-1)|\} \right\}\)，其中 \(l,r\) 中同时出现 \(s_1,s_2\) 的后缀，故双指针 \(l,r\)，单调队列维护 \(\text{height}\) 最小值即可。（或 \(O(1)\) 查，带预处理 log）

令 \(T=s_1+\texttt{\#}+s_2\)，用 KMP 处理出 \(s_3\) 在 \(T\) 中的所有出现

这时用第一种方法的话，再要求区间内没有完整出现 \(s_3\) 就行。一种方法是，若 \(s_3\) 在 \(T\) 中出现的一个起始位置为 \(x\)，那么改一下 \(\text{height}\)，要求 \(\text{height}(\text{rk}(x-i))<|s_3|+i\)，把这些要求 \(O(n)\) 并起来就行。

另一种方法是，设 \(f(i)\) 为 \(T\) 的后缀 \(i\) 不包含 \(s_3\) 的最长前缀长度，把 ans = max(ans, height[i]) 改成 ans = max(ans, min({height[i], f[sa[i - 1]], f[sa[i]]})) 就行了。

另另一种方法是，直接用个数据结构维护。

用第二种方法的话，一样的。