自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:12:08，当前版本为作者最后更新于2019-10-02 18:32:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里是官方题解。

题意 ： 给出 $n$ 个字符串 $S_1,S_2,...S_n$。

共有 $m$ 次询问，每次给出 $l,r$ 求字符串 $S_l,S_{l+1},...S_r$ 的最长公共子串长度。

$n\leq 2\times 10^5,m\leq 10^5,\sum_{i=1}^nS_i\leq 4\times 10^5$ ，时限 $\texttt{0.8s}$ ，空限 $\texttt{64Mb}$。

---

本题的 SAM 上两个自然根号做法，以及一个 ${\rm poly}(\log)$ 做法 /jy。

关于“自然根号”结论说明，可见 ： 分块相关杂谈。

小声说 ：这是 $\rm CmdOI2019$ 中唯一一个先有题面后有算法的题目。

• 做法①（std）： 分治

广告 : 后缀自动机学习笔记(应用篇)

• 前置知识 A ： 用 SAM 做 SP-LCS2

假设有 $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 好吃的题目 及相关题解。

• 原问题

并没有强制在线，考虑猫树分治。

(附 : 把分治树存下来，类似于猫树就可以做到强制在线了。但是所需空间较大，并不实用)

当分治到某个区间时 $[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:

特别神奇的是，下面这份代码我一遍写完就和暴力拍上了，可喜可贺。

#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 -永无岛

这里也简要地介绍一下该做法。

用 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)$ ，空间也是线性。

有空补代码。