题解 P5576 【[CmdOI2019]口头禅】
command_block
·
·
题解
这里是官方题解。
题意 ： 给出 n 个字符串 S_1,S_2,...S_n。
共有 m 次询问，每次给出 l,r 求字符串 S_l,S_{l+1},...S_r 的最长公共子串长度。
------------
本题的 SAM 上两个自然根号做法，以及一个 ${\rm poly}(\log)$ 做法 /jy。
关于“自然根号”结论说明，可见 ： [分块相关杂谈](https://www.luogu.com.cn/blog/command-block/fen-kuai-xiang-guan-za-tan)。
小声说 ：这是 $\rm CmdOI2019$ 中唯一一个先有题面后有算法的题目。
- ### **做法①**（std）： 分治
广告 : [后缀自动机学习笔记(应用篇)](https://www.luogu.com.cn/blog/command-block/hou-zhui-zi-dong-ji-xue-xi-bi-ji-ying-yong-pian-post)
- 前置知识 A ： 用 **SAM** 做 [SP-LCS2](https://www.luogu.org/problem/SP1812)
假设有 $n$ 个串，总长为 $len$ ，我们把某个串 $S$ 当做基准匹配串，剩下的是文本串。
对于其中一个匹配串 $T$ ，求 :
$slen[i]$ 表示 $S$ 中 $S[i-slen[i]+1,i]$ 在 $T$ 中出现过，即以 $i$ **结尾**的位置的**最长**匹配长度。
这是经典问题，用 $S$ 在 $T$ 的 SAM 中匹配一次即可求得，故不赘述。
最后将所有匹配串所得到的 $slen[i]$ 取 $\min$ ，最后把整个数组取 $\max$ 即可。
复杂度为 $O(|S|n+len)$ ，建 SAM 的总复杂度 $O(len)$ ，$S$ 要在每个串上跑匹配，复杂度是$O(|S|n)$。
很明显，选择这些字符串中长度最短的串做基准串，跑的最快。
- 前置知识 B ：猫树分治，又称二区间合并等。
可见 [P6240 好吃的题目](https://www.luogu.com.cn/problem/P6240) 及相关题解。
- 原问题
并没有强制在线，考虑猫树分治。
(附 : 把分治树存下来，类似于猫树就可以做到强制在线了。但是所需空间较大，并不实用)
当分治到某个区间时 $[l,r]$ ，选取关键串 $S_k,k\in[l,r]$。处理所有跨越 $k$ 的询问。
以 $S_k$ 为基准匹配串，分别向左向右匹配，求出各个 $slen$ 数组的“前缀 $\min$”
在求答案时，将询问区间的两个端点处的 $slen$ 前缀 $\min$ 合并，然后对整个数组取 $\max$ 即可。
这样，若分治时选择的 $S_k$ 较长，则复杂度会退化。直接使用取中点的普通分治是不可行的，考虑设计更好的分治策略 : **倍增分治**。
对于一个阈值 $x$ ，称长度小于等于 $2^x$ 的为短串，长度大于 $2^{x+1}$ 的为长串。显然长串的个数为 $O(len/2^x)$。
分治到某区间之后，找出所有短串，取其中间位置做基准串。这样分治直到区间里都是长串，将阈值 $x$ 增加 $1$。
接下来计算该算法的复杂度。首先考虑求 $slen$ 的部分。
观察分治树，对于一个 $x$ ，对应的短串在 $O(\log n)$ 层分治后就被耗尽。
而阈值为 $x$ 时，分治区间的总大小是 $O(len/2^x)$ 的，基准匹配串的长度为 $O(2^x)$ ，故花费的时间为 $O(2^x(len/2^x)\log n)=O(len\log n)$。
阈值 $x$ 共有 $O(\log len)$ 个，故总复杂度为 $O(len\log len\log n)$ 。
接下来考虑处理询问的复杂度。
分治中合并答案的复杂度为 $O(\text{对应基准串长度})$。
观察上面的分治，不难发现，一个询问区间所对应的基准串,不会超过区间中最短串的 $2$ 倍。(因为倍增嘛)
由最小值分治的结论，这里会产生一个自然根号。
即 ： 对询问记忆化后，复杂度为 $O(len\sqrt{m})$。
综上所述，总时间复杂度为 $O\big((len+m)\log len\log n+len\sqrt{m}\big)$ ，空间复杂度线性。
由于所有操作均为暴力 `for` 和取 $\min$ ，常数**较小**，可以轻松通过本题的数据范围。
**Code:**
特别神奇的是，下面这份代码我一遍写完就和暴力拍上了，可喜可贺。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#define MaxS 400500
#define MaxM 100500
#define MaxN 20500
using namespace std;
inline int read()
{
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct Node
{int t[2],f,len;}a[MaxS<<1];
int tn;
struct SAM
{
int las,root;
void add(int c)
{
int np=++tn,p=las; las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=root;
else {
int v=a[p].t[c];
if (a[p].len+1==a[v].len)a[np].f=v;
else {
int nv=++tn; a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[v].f=a[np].f=nv;
}
}
}
void build(char *str,int len)
{
las=root=++tn;
for (int i=0;i<len;i++)
add(str[i]-'0');
}
}t[MaxN];
char _str[MaxS],*sp=_str,*str[MaxN];
int ans[MaxM],len[MaxN];
struct Data
{int l,r,pos;}b[MaxM],bl[MaxM],br[MaxM];
int _slen[MaxS<<3],*slen[MaxN],*lenp;
int tp[MaxN];
map<pair<int,int>,int> sav;
void solve(int l,int r,int tl,int tr,int lim)
{
if (tl>tr)return ;
int tot=0;
while(1){
for (int i=l;i<=r;i++)
if (len[i]<=lim)tp[++tot]=i;
if (tot)break;
else lim<<=1;
}int mid=tp[(tot+1)/2];
lenp=_slen;
for (int i=l;i<=r;i++){
slen[i]=lenp;
lenp+=len[mid]+1;
}for (int i=0;i<len[mid];i++)slen[mid][i]=i+1;
for (int i=mid-1,p,plen;i>=l;i--){
p=t[i].root;plen=0;
for (int j=0,c;j<len[mid];j++){
c=str[mid][j]-'0';
if (!a[p].t[c]){
while(p!=t[i].root&&!a[p].t[c])p=a[p].f;
plen=a[p].len;
}
if (a[p].t[c]){
p=a[p].t[c];plen++;
}slen[i][j]=min(slen[i+1][j],plen);
}
}
for (int i=mid+1,p,plen;i<=r;i++){
p=t[i].root;plen=0;
for (int j=0,c;j<len[mid];j++){
c=str[mid][j]-'0';
if (!a[p].t[c]){
while(p!=t[i].root&&!a[p].t[c])p=a[p].f;
plen=a[p].len;
}
if (a[p].t[c]){
p=a[p].t[c];plen++;
}slen[i][j]=min(slen[i-1][j],plen);
}
}
int nl=0,nr=0;
for (int i=tl;i<=tr;i++){
if (b[i].l<=mid&&mid<=b[i].r){
pair<int,int> kk=make_pair(b[i].l,b[i].r);
if (sav.count(kk))
ans[b[i].pos]=sav[kk];
else {
int ret=0;
for (int j=0;j<len[mid];j++)
ret=max(ret,min(slen[b[i].l][j],slen[b[i].r][j]));
sav[kk]=ans[b[i].pos]=ret;
}
}else if (b[i].r<mid)bl[++nl]=b[i];
else br[++nr]=b[i];
}int tmid=tl+nl-1;
for (int i=1;i<=nl;i++)b[tl+i-1]=bl[i];
for (int i=1;i<=nr;i++)b[tl+nl+i-1]=br[i];
solve(l,mid-1,tl,tl+nl-1,lim);
solve(mid+1,r,tl+nl,tl+nl+nr-1,lim);
}
int n,m;
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++){
scanf("%s",str[i]=sp);
len[i]=strlen(sp);
t[i].build(str[i],len[i]);
sp+=len[i];
}
for (int i=1;i<=m;i++){
b[i].l=read();b[i].r=read();
b[i].pos=i;
}
solve(1,n,1,m,10);
for (int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
```
**附** ： 利用 $slen$ 数组也可求出区间本质不同公共子串数目。留做习题。
- ### **做法②** ： 广义 SAM + 扫描线
对于广义 SAM 上的节点 $u$ ，记 $P_u$ 为在 $parent$ 树中 $u$ 子树内存在终止节点的串的集合。
当询问区间 $[l,r]$ 时，若 $[l,r]\subseteq P_u$ ，则点 $u$ 可以向答案贡献。
考虑逐步增大 $r$ ，维护每个 $l$ 的答案。
对于 SAM 上的点 $u$ ，记 $P_u$ 中从 $r$ 向前的极长连续段的左端点为 $l_u$。
在询问 $[l,r]$ 时，若 $l_u\leq l$ 则点 $u$ 能贡献。
这里又有一个自然根号 ： 广义 SAM 上 $\sum_u |T_u|$ 是 $O(len\sqrt{len})$ 级别的。
于是，在 $r$ 增加时，对所有 $P_u$ 中含 $r$ 的点暴力更新即可。
有 $O(len\sqrt{len})$ 次单点修改，$O(m)$ 次区间查 $\rm max$ ，使用 $O(1)-O(\sqrt{n})$ 分块，复杂度为 $O(len\sqrt{len}+m\sqrt{n})$。
卡常后可以通过本题。
- ### **做法③** ： 广义 SAM + 线段树
可见 [（Mina）【题解】[CmdOI2019] 口头禅 广义 SAM -永无岛](https://www.mina.moe/archives/13606)
这里也简要地介绍一下该做法。
用 `std::set` 维护 $P_u$ 中的连续段，然后启发式合并。这部分复杂度为 $O(len\log len\log n)$。
按照节点的 $len$ 从大到小枚举，由于 $parent$ 树上 $len$ 从深到浅递减，故按这个顺序也可以顺便进行合并。
每次合并后，若产生新的连续段（该事件最多会发生 $O(len)$ 次），回答所有当前节点能够贡献到的询问，然后将这些询问删除。
使用线段树维护询问，将询问 $[l,r]$ 挂在位置 $l$ ，权值为 $r$。
需要寻找 $[L,R]$ 包含的所有询问时，查询 $[L,R]$ 内的权值最小值 $c$ ，若 $c\leq R$ ，则说明找到了一个合适的区间。
则复杂度为 $O(len\log len\log n)$ ，空间也是线性。
有空补代码。