专栏文章

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

ccommand_block
个人记录参与者 19已保存评论 18

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
18 条
当前快照
1 份
快照标识符
@mmd2cpq0
此快照首次捕获于
2026/03/05 14:07
3 天前
此快照最后确认于
2026/03/05 14:07
3 天前
查看原文
请配合 后缀自动机学习笔记(干货篇) 与 题单:SAM练习题 食用。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

4. SAM\rm SAM 的初级应用

历经千辛万苦构造出了 SAM\rm SAM ,它能干什么呢?
  • Δ4.1\color{blue}\bf \Delta 4.1 解决单文本多次匹配的问题
众所周知, SAM\rm SAM 是一个能够匹配所有子串的自动机。
首先建立出文章串的 SAM\rm SAM ,按照自动机的定义直接匹配即可,复杂度O(n+m)O(n+m),mm是询问串总长。
代码就不放了,毕竟太模板了……
比较套路的一道题目。
  • 思路1: SAM\rm SAM 是个DAG,于是乎可以在上面DP。(不常用)
一般来讲,DAG上可能重复转移,是很难跑计数DP的。
但是我们知道后缀自动机的性质 : 任意两个节点的表示集合没有交。
所以,从某个节点(不一定要求是源点)出发的路径组成的串,都是互不相同的,如果相同的话,就违背了上述性质。
所以我们只要统计路径数即可,不需要考虑重复问题。
设 f[u]f[u] 表示从 uu 出发的路径数,包括从 uu 到 uu (空串)。
DP的时候令 f[u]+=f[son]f[u]+=f[son] 即可,最后还要加上自己到自己的 11。
不过题目中不算空串,那么 f[1]−1f[1]-1 就是答案。
Code:
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 100500
using namespace std;
int n;
char str[MaxN];
struct Node
{int t[26],f,len;}
a[MaxN<<1];
int las,tn;
void add(int c)
{
  int p=las,np=++tn;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=1;//case 1
  else {
  	int v=a[p].t[c];
  	if (a[v].len==a[p].len+1)a[np].f=v;//case 2
  	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[np].f=a[v].f=nv;//case 3
    }
  }
}
long long f[MaxN<<1];
void dfs(int u)
{
  if (f[u])return ;
  for (int i=0,v;i<26;i++)
  	if (v=a[u].t[i])
	  {dfs(v);f[u]+=f[v];}
  f[u]++;
}
int main()
{
  scanf("%d%s",&n,str);las=tn=1;
  for (int i=0;i<n;i++)add(str[i]-'a');
  dfs(1);
  printf("%lld",f[1]-1);
  return 0;
}
  • 思路2: SAM\rm SAM 每个节点表示的串没有交集,而且一定表示了所有的串。
那我们把所有节点表示的串的个数(类大小)加起来就好了,
考虑到 minlen(u)=maxlen(fa)+1minlen(u)=maxlen(fa)+1 ,我们统计 ∑u(u.len−u.fa.len)\sum\limits_{u}(u.len-u.fa.len)即可。
这种方法需要对 SAM\rm SAM 的基本性质比较熟悉,同时也很经典,建议好好理解。
Code:
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 100500
using namespace std;
int n;
char str[MaxN];
struct Node
{int t[26],f,len;}
a[MaxN<<1];
int las,tn;
void add(int c)
{
  int p=las,np=++tn;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=1;//case 1
  else {
  	int v=a[p].t[c];
  	if (a[v].len==a[p].len+1)a[np].f=v;//case 2
  	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[np].f=a[v].f=nv;//case 3
    }
  }
}
int main()
{
  scanf("%d%s",&n,str);las=tn=1;
  for (int i=0;i<n;i++)add(str[i]-'a');
  long long ans=0;
  for (int i=1;i<=tn;i++)ans+=a[i].len-a[a[i].f].len;
  printf("%lld",ans);
  return 0;
}
我们知道每个点代表着一个 edp\rm edp 等价类。
显然有 : edp\rm edp 集合大小 (比较常用,后面称为 siz ) 就是这点包含的一堆字子串(在原串中)的出现次数。
如何统计 siz 呢?我们考虑parent\rm parent树上一遍树形DP:
先把每个前缀所属的点的 siz 设为11,可以证明这些点是前缀对应的 edp\rm edp 出现的parent\rm parent树上最深的点,因为无法在这些前缀前面加东西。
称这些点为前缀节点,每个前缀节点代表一个 edp\rm edp。
( 事实上,有且仅有某个前缀节点的祖先拥有该 edp\rm edp,这在后面会详细讲 )
然后 u.siz+=son.siz ,子树求和即可。
这需要把树建出来,常数较大。
另外一种常数更小的方法是:先按照len排序,然后len大的先贡献。
由于 fa.len>u.lenfa.len>u.len 正确性显然。
这个排序如果用 std::sort 的话复杂度反而会带 loglog ,那就得不偿失了。
观察到所有的 len≤nlen\leq n ,不妨使用基数排序。
但是这种方法有一定的局限性,比如说广义 SAM\rm SAM 用不了,某些时候操作麻烦等等……
我们也维护了某个点的最长串 len ,统计 max⁡u[u.siz<1](u.siz∗u.len)\max\limits_u[u.siz<1](u.siz*u.len) 即可。
Code:
这里只提供树形dp版,基排版可以到其他题目里面找。
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 1005000
using namespace std;
struct Node
{int t[26],f,len,siz;}
a[MaxN<<1];
int tn,las;
void add(int c)
{
  int p=las,np=++tn;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=1;
  else {
    int v=a[p].t[c];
    if (a[v].len==a[p].len+1)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[np].f=a[v].f=nv;
    }
  }
}
vector<int> g[MaxN<<1];
ll ans;
void dfs(int u)
{
  for (int i=0,v;i<g[u].size();i++){
   	dfs(g[u][i]);
   	a[u].siz+=a[g[u][i]].siz;
  }
  if (a[u].siz>1)
    ans=max(ans,1ll*a[u].siz*a[u].len);
}
int n;
char str[MaxN];
int main()
{
  scanf("%s",str+1);
  n=strlen(str+1);
  las=tn=1;
  for (int i=1;i<=n;i++)add(str[i]-'a');
  for (int i=1,p=1;i<=n;i++){
  	p=a[p].t[str[i]-'a'];
  	a[p].siz=1;
  }for (int i=2;i<=tn;i++)
    g[a[i].f].push_back(i);
  dfs(1);
  printf("%lld\n",ans);
  return 0;
}
首先这个翻译非常的假,人话题意:本质不同子串出现次数的平方和
对于 SAM\rm SAM 上的节点,计算∑uu.siz2∗(u.len−fa.len)\sum\limits_{u}u.siz^2*(u.len-fa.len)即可。
评测记录
题意 : 不断push_back字符,每次统计本质不同子串数。
( 这道题字符集很大,需要使用 std::map 建立后缀自动机 )
上文4.24.2中,我们讲到 ANS=∑u(u.len−u.fa.len)ANS=\sum\limits_{u}(u.len-u.fa.len)
那么每次有 lenlen 变化的时候,维护这个总和就好了。
首先新建 np 的时候,ans+=a[np].len;
然后对于case 1,2,我们没有新建节点,只是加入了一条f指针,所以ans-=a[a[np].f].len
对于case 3,我们新建了 nv ,要使ans+=a[nv].len;,
但是它只有两个儿子 v 和 np ,又需要ans-=2*a[nv].len;
又考虑到a[np].f=nv,其实还是ans-=a[a[np].f].len;
综上,每次add之后令ans+=a[np].len-a[a[np].f].len;即可。
评测记录
细节比较的多TAT
我们考虑使用类似线段树上二分的办法,在 SAM\rm SAM 上跳(建议结合代码理解)。
已经到达了某个点,我们从 a~z 枚举出边,选定后,当前剩余的 kk 要减去字典序比当前构造串小的串的个数。
注意在开始选择路径之前,还得要减去一些东西(详见代码)……
问题就在于减掉多少。设 f[u]f[u] 表示从 uu 出发能得到的字符串个数。
  • t=0t=0 ,本质相同子串只算一次
这很好办, f[u]=f[u]=从该点出发的路径总条数,这个按照4.2.14.2.1dp出来。
  • t=1t=1 ,本质相同子串算多次
开始麻烦了……我们知道一个子串 ss 的出现次数=edp(s)={\rm edp}(s)
那么我们就是要统计DAG上 uu 的一颗子DAG内, ∑path:u→vv.siz\sum\limits_{path:u\rightarrow v}v.siz
也就是每一个串(路径)的贡献是 : 终点的 ∣edp∣|edp| ,即siz。
采用4.34.3的方法计算siz即可。
那么如何统计呢?这也好办,4.2.14.2.1中空串的贡献是11,现在改成siz就可以了。
如何判断无解?这道题同样不计空串,我们要在 f[1]f[1] 内把空串的贡献去掉,然后 f[1]<kf[1]<k 即无解(一共没有 kk 个满足题意的子串)。
注意其他点空串的贡献是不能去掉的,因为空串表示停止在该点。
评测记录

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

5. SAM\rm SAM 与AC自动机的相似性

回忆 : 自动机某个点表示的串,是指从根到该点的路径构成的所有串。
众所周知,AC自动机的 fail 指针指向的地方,是该节点表示的串的最长后缀,也就是把前面去掉(尽可能少的)一点。
我们注意到 SAM\rm SAM 的fa指针有同样的性质 : 儿子是由父亲在前面加字符产生的,那么父亲就可以视作在儿子前面去掉字符。
我们完全可以把 SAM\rm SAM 理解为把某个串的所有子串建立AC自动机。
这有什么用呢? 来看一下例题吧:
我们把两个串分别称作 S1,S2S1,S2.
对于 S2S2 设一个数组为 slen[1...∣S2∣]slen[1...|S2|].
slen[i]slen[i] 表示 S1S1 中 S1[i−slen[i]+1,i]S1[i-slen[i]+1,i] 在 S2S2 中出现过,即以 ii 结尾的位置的最长匹配长度。
即“每个前缀匹配出的最长后缀”,不难发现, slenslen 数组的 max⁡\max 就是答案。
怎么求呢?对 S1S1 建立 SAM\rm SAM ,然后当做AC自动机来用。
把 S2S2 拿到上面跑匹配,如果当前节点有出边,则匹配长度++
否则,跳fail直到有出边为止,匹配长度变为该点的len+1。
如果回到根还是不能匹配,匹配长度是 00.
(具体见代码)
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 250500
using namespace std;
struct Node
{int t[26],f,len;}a[MaxN<<1];
int tn,las;
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=1;
  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;
    }
  }
}
int slen[MaxN],len1,len2;
char s1[MaxN],s2[MaxN];
int main()
{
  scanf("%s%s",s1,s2);
  len1=strlen(s1);len2=strlen(s2);
  tn=las=1;
  for (int i=0;i<len1;i++)add(s1[i]-'a');
  //构造 $\rm SAM$  
  int p=1,plen=0;//当前点,匹配长度 
  for (int i=0,c;i<len2;i++){
    c=s2[i]-'a';
    if (!a[p].t[c]){
      while(p!=1&&!a[p].t[c])p=a[p].f;
      plen=a[p].len;
      //如果没有转移边,不断跳fail 
    }
    if (a[p].t[c]){
      p=a[p].t[c];plen++;
      //能匹配,plen++ 
    }slen[i]=plen;
  }
  int ans=0;
  for (int i=0;i<len2;i++)ans=max(ans,slen[i]);
  printf("%d",ans);
  return 0;
}

5.2 SP1812 LCS2 - 多串最长公共子串

类似地,把第一个串当做匹配串,其他的串建立 SAM\rm SAM
把第一个串在每个 SAM\rm SAM 上跑匹配,slenslen 对当前匹配长度取min⁡\min。
最终回答整个 slenslen 的 max⁡\max。
代码奇短无比,比SA+单队不知高到哪里去了。
AC记录

5.3 CF235C Cyclical Quest

题意 : 给出一个文本串和若干询问串,求每个询问串的所有本质不同循环,能够匹配到的次数。
先不考虑本质不同这件事。
循环就是把询问串第一个字符拿去放在最后面。
可以视为,先把目前匹配到的串的第一个字符删掉,然后再加上一个。
如果目前这个串根本没有在文本中完整出现,那么这个删除操作可以忽略。
否则,len--,如果删了前面之后 lenlen 不在当前节点区间((u.fa.len,u.len](u.fa.len,u.len])里面了就跳 f。
(在前面删掉字符?这不就是parent tree跳f的性质吗!)
加字符的操作同上。
(太有趣了,双端队列?很有出题价值![笑])
最后把匹配到的所有节点 sizsiz 加在一起就好了。
还要考虑去重问题,这也好办 : 如果同一个询问串多次匹配到同一个节点,贡献只算一次,具体可以打标记实现。
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 1000500
using namespace std;
struct Node
{int t[26],len,f,siz;}a[MaxN<<1];
int tn,las;
void add(int c)
{
  int p=las,np=++tn; 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=1;
  else {
    int v=a[p].t[c];
    if (a[v].len==a[p].len+1)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[np].f=a[v].f=nv;
    }
  }
}
vector<int> g[MaxN<<1];
void dfs(int num)
{
  for (int i=0;i<g[num].size();i++){
    dfs(g[num][i]);
    a[num].siz+=a[g[num][i]].siz;
  }
}
char str[MaxN];int len;
int vis[MaxN<<1],T;
void solve()
{
  scanf("%s",str+1);
  len=strlen(str+1);
  int slen=0,p=1;
  for (int i=1;i<=len;i++){
    str[i]-='a';
    while(p>1&&!a[p].t[str[i]])
      slen=a[p=a[p].f].len;
    if (a[p].t[str[i]]){
      p=a[p].t[str[i]];
      slen++;
    }
  }long long ans=0;
  for (int i=1;i<=len;i++){
    if (slen==len){
      if (vis[p]!=T)ans+=a[p].siz;
      vis[p]=T;
      if (--slen==a[a[p].f].len)
        p=a[p].f;
    }while(p>1&&!a[p].t[str[i]])
      slen=a[p=a[p].f].len;
    if (a[p].t[str[i]]){
      p=a[p].t[str[i]];
      slen++;
    }
  }printf("%I64d\n",ans);
}
int main()
{
  scanf("%s",str+1);
  len=strlen(str+1);
  tn=las=1;
  for (int i=1;i<=len;i++)add(str[i]-='a');
  for (int i=2;i<=tn;i++)g[a[i].f].push_back(i);
  for (int i=1,p=1;i<=len;i++)
    a[p=a[p].t[str[i]]].siz=1;
  dfs(1);
  scanf("%d",&T);T++;
  while(--T)solve();
  return 0;
}

5.4 P6640 [BJOI2020] 封印

先建立 SS 的 SAM\rm SAM ,然后让 TT 在上面跑匹配,求出 TT 的每个前缀 ii 能够匹配的后缀长度 sl[i]sl[i]。
对于区间 [l,r][l,r] 的限制,答案是 max⁡i=lrmin⁡(sl[i],i−l+1)\max\limits_{i=l}^r\min(sl[i],i-l+1)。
可以二分答案 midmid , 然后 ii 必须满足 i−l+1≥midi-l+1\geq mid 即 i≥mid+l−1i\geq mid+l-1。
若满足这个要求,那么 i+l+1i+l+1 的约束就可以不考虑了,变成一个区间 max⁡\max 问题,可以用 STST 表做到 O(1)O(1)。
复杂度 O(nlog⁡n)O(n\log n)。[评测记录] ()

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

6. SAM\rm SAM 构建后缀树

SAM\rm SAM 并不是万能的,有些时候使用后缀数据结构家族的另两个成员 : 后缀树/后缀数组 才能够更快更好地解决问题。
问题在于,同时掌握这三个东西也太麻烦了趴!!! 而且 SAM\rm SAM 代码又短又简洁,用惯了就容易忘掉其他的东西……
万幸的是,有用 SAM\rm SAM 来构造后缀树的方法,真是造(bao)福(fu)社会啊!
有一个很好用的结论:反串的 SAM\rm SAM 的parent树就是后缀树。
严谨证明的话咱这里没有……但是可以感性理解 :
parent树有一个性质,父亲是孩子的最长后缀( edp\rm edp 不同)。
而把串翻转过来之后,反串的parent树就满足 : 父亲是孩子的最长前缀 ( beginposbeginpos 不同 )。
观察压缩后缀树的定义, bgp\rm bgp 相同的两个串才能被压缩,所以 SAM\rm SAM 和后缀树其实是有异曲同工之妙的!
另一个构造后缀树的算法是Ukk,复杂度同样要依赖字符集大小,因此, SAM\rm SAM 构造法几乎可以完全替代Ukk。(naive了,花样其实还有很多)
这里还要讲一些性质。
  • 设 lcs(i,j)lcs(i,j) 为前缀 i,ji,j 的最长公共后缀长度,其等于parent\rm parent树上 LCA 的 lenlen 值。
例题 : P4248 [AHOI2013]差异
这道题可以转化为求两两后缀的 lcplcp 和。
众所周知,这就相当于求后缀树上两两叶节点的 lcalca 深度总和。
建立后缀树之后,写一个树形dp就可以搞定了:
Code:
CPP
#include<cstring>
#include<vector>
#include<cstdio>
#define MaxN 500500
using namespace std;
struct Node
{int t[26],f,len;}a[MaxN*2];
int tn,las;
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=1;
  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;
    }
  }
}
long long sum;
int siz[MaxN*2];
vector<int> g[MaxN*2];
void dfs(int num)
{
  int sav=siz[num];
  for (int i=0;i<g[num].size();i++){
    dfs(g[num][i]);
    siz[num]+=siz[g[num][i]];
  }
  for (int i=0;i<g[num].size();i++)
    sum+=1ll*siz[g[num][i]]*(siz[num]-siz[g[num][i]])*a[num].len;
  sum+=1ll*sav*(siz[num]-sav)*a[num].len;
}
char str[MaxN];int len;
int main()
{
  scanf("%s",str);len=strlen(str);
  las=tn=1;
  for (int i=len-1;i>=0;i--)add(str[i]-'a');
  for (int i=len-1,p=1;i>=0;i--){
    p=a[p].t[str[i]-'a'];
    siz[p]++;
  }
  for (int i=2;i<=tn;i++)
    g[a[i].f].push_back(i);
  dfs(1);
  printf("%lld",1ll*(len-1)*len*(len+1)/2-sum);
  return 0;
}
附 : [DS记录]P5284 [十二省联考2019]字符串问题 (后缀树优化建边)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

7.广义 SAM\rm SAM

广义 SAM\rm SAM 定义 : 给出多个串,求一个能够识别这些串所有子串的自动机。
构造方法奇为暴力 :
每次加入一个串前,把las设为1。
正确性显然(雾)
补记 : 我naive了,Trie树上正牌的广义SAM一点都不会,枯了……
例题 : SP8093 JZPGYZ - Sevenk Love Oimaster
首先对于所有模板串建立广义 SAM\rm SAM ,求出每个点中有多少类模板串的子串,设为siz。
对于匹配串在 SAM\rm SAM 上跳,假如跳到空则输出0,否则输出siz。
怎么求呢? 我们对第 ii 个模板串后缀对应的点染上第 ii 种颜色,然后可以静态子树数颜色。
附 : CF427D Match & Catch (近乎广义 SAM\rm SAM 模板)
还有一个奇怪的题 : Loj#6071. 「2017 山东一轮集训 Day5」字符串
先考虑单个串怎么做,前面我们讲过了可以parent\rm parent树,或者自动机DAG路径计数。
对于多个子串拼接的情况,我们无法构建类似parent\rm parent的强有力的结构,而DAG路径计数更加简单粗暴,只需要满足自动机的基本性质即可。
我们考虑先对每个串单独建立 SAM\rm SAM ,考虑这个DAG的意义,就是从根开始的路径=字符串的每个子串(不重不漏)。
有考虑另一种能跳跃拼接的字符串数据结构 : 子序列自动机。
其做法就是从每个位置'c'的出边向后连接到最近的一个'c'。
那么,我们考虑把这个若干个 SAM⋅DAG\rm SAM·DAG 魔改一下。
如果某个点没有'c'出边,那么连向后面第一个满足要求的的DAG源点的'c'出边。
引用某位大佬的话 :
现在我们建出来的DAG就非常牛逼了,如果发现想走某一条转移边而没有办法走的时候,它会自动跳到下一个字符串上去,我们在这张DAG上求一下路径总数就是答案了。
看起来很有出题价值。
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define mod 1000000007
#define sf scanf
#define pf printf
#define MaxN 1005000
using namespace std;
struct Data
{int f,len,t[26];}a[MaxN<<1];
int tn,las,rt[MaxN],frt;
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=frt;
  else {
    int v=a[p].t[c];
    if (a[v].len==a[p].len+1)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;
    }
  }
}
long long dp[MaxN<<1];
void dfs(int u)
{
  if (dp[u])return ;
  for (int k=0,v;k<26;k++)
    if (v=a[u].t[k]){
      dfs(v);
      dp[u]+=dp[v];
    }
  dp[u]=(dp[u]+1)%mod;
}
int n,tp[26];
char str[MaxN];
int main()
{
  sf("%d",&n);
  for (int i=1,len;i<=n;i++){
    sf("%s",str);
    rt[i]=frt=las=++tn;
    len=strlen(str);
    for (int j=0;j<len;j++)
      add(str[j]-'a');
  }rt[n+1]=tn+1;
  for (int i=n;i;i--){
    for (int j=rt[i];j<rt[i+1];j++)
      for (int k=0;k<26;k++)
        if (!a[j].t[k])
          a[j].t[k]=tp[k];
    for (int k=0;k<26;k++)
      tp[k]=a[rt[i]].t[k];
  }dfs(1);
  pf("%lld",dp[1]);
  return 0;
}

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

8.线段树合并维护edp

我们发现 parent\rm parent 树上,父节点的 edp\rm edp 恰恰是子节点的 edp\rm edp 求并,这和树上线段树合并太像了!
我们可以考虑使用线段树合并来维护 edp\rm edp 集合,来干一些神奇的事。
例题 : CF1037H Security
题意 : 给一个文章串SS,给出若干文本串TT。
截取 SS 的一个字串 S2=S[l...r]S2=S[l...r] ,求 S2S2 的子串中,严格大于 TT 的字典序最小的串,如果没有输出-1。
  • 我们先考虑没有截取限制,即 S2=SS2=S。
那么,有一个显而易见的贪心:
先建立SS的 \rm SAM$$,然后让T在在S上面跑匹配,我们假设在上面跑匹配,我们假设在T_p$配不上了。
找一个大于当前TpT_p那个字符的最小字符放在串尾即可。
问题在于可能候选的字符都是小于TpT_p的,那我们只能退而求其次,退回上一位,再看看有那个位置没有大于Tp−1T_{p-1}的。
如果退到源点还是没有方案,那么输出-1。
具体的复杂度是O(∣S∣+26∗∑∣T∣)O(|S|+26*\sum|T|),那个2626远远跑不满。
  • 现在考虑截取限制,即 S2=S[l...r]S2=S[l...r]。
如果我们知道 S[l...r]S[l...r] 的 SAM\rm SAM ,我们就可以套用上述贪心了,但是每次重构复杂度显然不对。
还是要先建立 SS 的 SAM\rm SAM ,我们称包含任意一个 S[l...r]S[l...r] 子串的点为“好点”。
那么我们发现,加入我们把所有的“不好点”以及相关的边删掉,那么我们就得到了 S[l...r]S[l...r] 的 SAM\rm SAM 。
这玩意虽然不保证点数边数为 O(∣S[l...r]∣)O(|S[l...r]|) ,但还是能恰好匹配所有子串的! (一个合法的自动机)
我们考虑设计一个函数,能够判定某个点是否为好点,那样的话就可以实现上述贪心操作了。
如何判断呢?我们采用线段树合并来维护每个点的 edp\rm edp 集合,具体做法就是在parent\rm parent树上由下而上合并线段树,空间受得住。注意合并的时候不能销毁儿子的树。
(当然用普通平衡树启发式合并也是可以的,不过代码长,复杂度还多个log⁡\log)
我们只要在线段树上区间查询一下 edp\rm edp 有没有值就好了,区间是 [l+len−1,r][l+len-1,r] 。这里 lenlen 是目前字符串的长度。
那么复杂度就是O(∣S∣logn+26∗∑∣T∣logn)O(|S|logn+26*\sum|T|logn),看起来比较险,其实由于数据水是极松的。
Code:
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 200500
using namespace std;
int n,q;
char str[MaxN],st[MaxN];
struct  $\rm SAM$ _Node
{int t[26],f,len,edp,rt;}
a[MaxN<<1];
int las,tn;
void add(int c)
{
  int p=las,np=++tn;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=1;//case 1
  else {
  	int v=a[p].t[c];
  	if (a[v].len==a[p].len+1)a[np].f=v;//case 2
  	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[np].f=a[v].f=nv;//case 3
    }
  }
}
vector<int> g[MaxN<<1];
struct SGT_Node
{int l,r;}b[MaxN*41];
int tot;
int marge(int x,int y)
{
  if (!x||!y)return x|y;
  int pos=++tot;
  b[pos].l=marge(b[x].l,b[y].l);
  b[pos].r=marge(b[x].r,b[y].r);
  return pos;
}
int to;
void add(int l,int r,int &num)
{
  if (!num)num=++tot;
  if (l==r)return ;
  int mid=(l+r)>>1;
  if (to<=mid)add(l,mid,b[num].l);
  else add(mid+1,r,b[num].r);
}
int wfl,wfr;
bool query(int l,int r,int num)
{
  if (!num)return 0;
  if (wfl<=l&&r<=wfr)return 1;
  int mid=(l+r)>>1;
  if (wfl<=mid&&query(l,mid,b[num].l))return 1;
  if (mid<wfr&&query(mid+1,r,b[num].r))return 1;
  return 0;
}
bool check(int num,int len)
{
  bool ans;
  wfl+=len-1;
  if (wfl>wfr)ans=0;
  else ans=query(1,n,a[num].rt);
  wfl-=len-1;
  return ans;
}
void dfs(int num)
{
  if (a[num].edp){
    to=a[num].edp;
    add(1,n,a[num].rt);
  }
  for (int i=0,v;i<g[num].size();i++){
    dfs(v=g[num][i]);
    a[num].rt=marge(a[num].rt,a[v].rt);
  }
}
int sp[MaxN];
int main()
{
  scanf("%s%d",str,&q);las=tn=1;
  n=strlen(str);
  for (int i=0;i<n;i++)add(str[i]-'a');
  for (int i=0,p=1;i<n;i++){
    p=a[p].t[str[i]-'a'];
    a[p].edp=i+1;
  }for (int i=2;i<=tn;i++)
    g[a[i].f].push_back(i);
  dfs(1);
  for (int qt=1,p,sav,len;qt<=q;qt++){
    scanf("%d%d%s",&wfl,&wfr,st);
    len=strlen(st);sp[sav=0]=p=1;
    for (int i=0;i<len;i++)st[i]-='a';
    for (int i=0,v;i<len;i++){
      v=a[p].t[st[i]];
      if (v&&check(v,i))sp[sav=i+1]=p=v;
      else break;
    }
    st[len]=-1;
    char las=100;
    for (;las==100&&sav>=0;sav--){
      p=sp[sav];
      for (int j=st[sav]+1,v;j<26;j++)
        if ((v=a[p].t[j])&&check(v,sav+1))
          {las=j;break;}
    }
    if (las==100)puts("-1");
    else {
      for (int i=0;i<=sav;i++)putchar(st[i]+'a');
      putchar(las+'a');putchar('\n');
    }
  }return 0;
}
先把原串倒过来,现在问题变成了 [a,b][a,b] 的子串在 [c,d][c,d] 中匹配的最长后缀。
考虑二分一个 lenlen ,就变成了 O(log⁡n)O(\log n) 个 [d−len+1,d][d-len+1,d] 在 [a+len−1,b][a+len-1,b] 中的存在性问题。
令 c′=d+len−1;a′=a+len−1c'=d+len-1;a'=a+len-1.
建立 SAM\rm SAM ,跑一个线段树合并求出每个点的 edp\rm edp。
然后定位包含子串 [c′,d][c',d] 的那个点,具体方法 : 先找出前缀 dd 的对应结束点,然后看 len 在parent\rm parent树上倍增。
定位到之后,在当前点看一看有没有 edp\rm edp 在给出的 [a′,b][a',b] 内,线段树上一个区间查询就好了。
复杂度 O(nlog2n)O(nlog^2n) ,常数较大。
评测记录
结论 ： 若 edpedp 中两两元素最小的差为 gg，那么对答案的贡献即为 ⌊len−gg⌋\left\lfloor\dfrac{len-g}{g}\right\rfloor。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

9.SAM上树分治

当你要统计前缀对子之间的贡献时,你会发现往往与 lcslcs(最长公共后缀) 有关。
而这又能转化成关于parent\rm parent树上LCA的一些信息,那么我们就可以使用有根树分治来统计。
某些时候也可以直接树剖。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

10.技巧大杂烩

10.1 P4081 [USACO17DEC]Standing Out from the Herd

设这些串分别为 S1...nS_{1...n} ,那么构造出 S[1,i)S_{[1,i)} 的广义 SAM\rm SAM 。
然后,利用 SAM\rm SAM 与AC自动机的相似性,把 SiS_{i} 在 S[1,i)S_{[1,i)} 的广义 SAM\rm SAM 上匹配一下,然后得到某个前缀在其他串上的匹配长度(取max⁡\max)。
对于 S(i,n]S(i,n] 的的广义 SAM\rm SAM 也进行同样的匹配操作。
最终可以得到每个串的每个后缀在其他串上的最长匹配长度。
最后对于每个串单独建立 SAM\rm SAM 判重。
具体来讲,就是先随意求出每个点的任意一个 edp\rm edp ,然后贡献就是根据长度和匹配长度比较,大于匹配长度的那部分才是该串独有的,计入贡献。
评测记录

10.2 P4770 [NOI2018]你的名字

题意: 给出一个文本串和若干询问串,求该询问串没有在文本串某个区间中匹配的本质不同子串个数。
首先弱化一下,不考虑那个区间限制。
做法和上一题差不多,先跑个后缀匹配,然后再对询问串建立 SAM\rm SAM 判重就好了。
问题在于现在加上了区间限制,按照套路,先线段树合并弄出 edp\rm edp 再说。
考虑一下我们匹配的时候究竟在做什么:
  • 跑匹配,也就是要知道能不能匹配,以及下一步的出边是什么。
  • 读取len,这样才知道究竟匹配了多长。
  • 发现没有出边,跳parentparent树。
我们要借用原有的 SAM\rm SAM 的框架,来做这三件事情。
在匹配的时候,我们直接取整个 SAM\rm SAM 的出边,然后用线段树查询一下目标节点在要求的区间内有没有 edp\rm edp ,注意这里和当前匹配长度也有关。
注意!失配了之后不能直接跳f,把匹配的长度减一后,还得再试一次,直到该节点的lenlen不对头为止。
怎么读取 lenlen 呢?
考虑到原有 SAM\rm SAM 节点表示的串 : 长度在某个区间内,且 edp\rm edp 在某某某的所有子串。
现在要求这些子串必须在某个区间内,那么这个长度区间的上界就要对某个东西取min⁡\min,因为最长的串前面一部分可能被砍掉了。这会破坏很多(?)性质。
而下界是不会变的,所以比较下界(fa.lenfa.len)就知道是否对头了。反正出边会检查,正确性是有保障的。
至于跳f这件事,直接在原自动机上跳就好了,可以证明复杂度是正确的(每跳一次匹配长度至少减一),而且不会丢信息。
CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define MaxN 1005000
using namespace std;
struct SAM_Node
{int t[26],f,len,edp,rt;};
int wfl,wfr,to;
long long ans=0;
struct SAM
{
  char str[MaxN];
  SAM_Node a[MaxN<<1];
  int las,tn,n;
  void add(int c)
  {
    int p=las,np=++tn;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=1;//case 1
    else {
    	int v=a[p].t[c];
    	if (a[v].len==a[p].len+1)a[np].f=v;//case 2
    	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[np].f=a[v].f=nv;//case 3
      }
    }
  }
  void buildSAM()
  {
    scanf("%s",str);
    n=strlen(str);las=tn=1;
    for (int i=0;i<n;i++)add(str[i]-'a');
    for (int i=0,p=1;i<n;i++){
      p=a[p].t[str[i]-'a'];
      a[p].edp=i+1;
    }for (int i=1;i<=tn;i++)g[i].clear();
    for (int i=2;i<=tn;i++)
      g[a[i].f].push_back(i);
  }
  void dfsedp(int num)
  {
    for (int i=0,v;i<g[num].size();i++){
      dfsedp(v=g[num][i]);
      a[num].edp=max(a[num].edp,a[v].edp);
    }
  }
  void build1()
  {buildSAM();dfsedp(1);}
  struct SGT_Node
  {int l,r,x;}b[MaxN*42];
  int tot;
  int marge(int x,int y)
  {
    if (!x||!y)return x|y;
    int pos=++tot;
    b[tot].x=max(b[x].x,b[y].x);
    b[pos].l=marge(b[x].l,b[y].l);
    b[pos].r=marge(b[x].r,b[y].r);
    return pos;
  }
  void add(int l,int r,int &num)
  {
    if (!num)num=++tot;
    b[num].x=max(b[num].x,to);
    if (l==r)return ;
    int mid=(l+r)>>1;
    if (to<=mid)add(l,mid,b[num].l);
    else add(mid+1,r,b[num].r);
  }
  vector<int> g[MaxN<<1];
  void dfs(int num)
  {
    if (a[num].edp){
      to=a[num].edp;
      add(1,n,a[num].rt);
    }
    for (int i=0,v;i<g[num].size();i++){
      dfs(v=g[num][i]);
      a[num].rt=marge(a[num].rt,a[v].rt);
    }
  }
  void build2()
  {buildSAM();tot=0;dfs(1);}
  int query(int l,int r,int num)
  {
    if (!num)return 0;
    if (wfl<=l&&r<=wfr)return b[num].x;
    int mid=(l+r)>>1,ans=0;
    if (mid<wfr)ans=max(ans,query(mid+1,r,b[num].r));
    if (!ans&&wfl<=mid)ans=max(ans,query(l,mid,b[num].l));
    return ans;
  }
  bool check(int num,int len)
  {
    int ans;
    wfl+=len-1;
    if (wfl>wfr)ans=0;
    else ans=query(1,n,a[num].rt);
    wfl-=len-1;
    return ans>0;
  }
  void clac(int *slen)
  {
    ans=0;
    for (int i=2;i<=tn;i++)
      if (slen[a[i].edp]<a[i].len)
        ans+=a[i].len-max(slen[a[i].edp],a[a[i].f].len);
  }
  void clear()
  {
    for (int i=1;i<=tn;i++){
      for (int j=0;j<26;j++)
        a[i].t[j]=0;
      a[i].f=a[i].len=a[i].edp=0;
    }
  }
}S,T;
int q,slen[MaxN];
int main()
{
  S.build2();
  scanf("%d",&q);
  while(q--){
    T.build1();
    scanf("%d%d",&wfl,&wfr);
    int p=1,len=0;
    for (int i=0,v;i<T.n;i++){
      v=T.str[i]-'a';
      while(1){
        if (S.check(S.a[p].t[v],len+1))
          {p=S.a[p].t[v];len++;break;}
        else {
          if (p==1){len=0;break;}
          len--;
          if (len==S.a[S.a[p].f].len)
            p=S.a[p].f;
        }
      }slen[i+1]=len;
    }
    T.clac(slen);
    printf("%lld\n",ans);
    T.clear();
  }return 0;
}

评论

共 18 条评论，欢迎与作者交流。

正在加载评论...