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

command_block · 2019-07-06 14:30:06 · 个人记录

请配合 后缀自动机学习笔记(干货篇) 与 题单:SAM练习题 食用。

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

4. \rm SAM 的初级应用

历经千辛万苦构造出了 \rm SAM ,它能干什么呢?

众所周知, \rm SAM 是一个能够匹配所有子串的自动机。

首先建立出文章串的 \rm SAM ,按照自动机的定义直接匹配即可,复杂度O(n+m),m是询问串总长。

代码就不放了,毕竟太模板了……

比较套路的一道题目。

• 思路1: \rm SAM 是个DAG,于是乎可以在上面DP。(不常用)

一般来讲,DAG上可能重复转移,是很难跑计数DP的。

但是我们知道后缀自动机的性质 : 任意两个节点的表示集合没有交。

所以,从某个节点(不一定要求是源点)出发的路径组成的串,都是互不相同的,如果相同的话,就违背了上述性质。

所以我们只要统计路径数即可,不需要考虑重复问题。

设 f[u] 表示从 u 出发的路径数,包括从 u 到 u (空串)。

DP的时候令 f[u]+=f[son] 即可,最后还要加上自己到自己的 1。

不过题目中不算空串,那么 f[1]-1 就是答案。

Code:

#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: \rm SAM 每个节点表示的串没有交集,而且一定表示了所有的串。

那我们把所有节点表示的串的个数(类大小)加起来就好了,

考虑到 minlen(u)=maxlen(fa)+1 ,我们统计 \sum\limits_{u}(u.len-u.fa.len)即可。

这种方法需要对 \rm SAM 的基本性质比较熟悉,同时也很经典,建议好好理解。

Code:

#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;
}

我们知道每个点代表着一个 \rm edp 等价类。

显然有 : \rm edp 集合大小 (比较常用,后面称为 siz ) 就是这点包含的一堆字子串(在原串中)的出现次数。

如何统计 siz 呢?我们考虑\rm parent树上一遍树形DP:

先把每个前缀所属的点的 siz 设为1,可以证明这些点是前缀对应的 \rm edp 出现的\rm parent树上最深的点,因为无法在这些前缀前面加东西。

称这些点为前缀节点,每个前缀节点代表一个 \rm edp。

( 事实上,有且仅有某个前缀节点的祖先拥有该 \rm edp,这在后面会详细讲 )

然后 u.siz+=son.siz ,子树求和即可。

这需要把树建出来,常数较大。

另外一种常数更小的方法是:先按照len排序,然后len大的先贡献。

由于 fa.len>u.len 正确性显然。

这个排序如果用 std::sort 的话复杂度反而会带 log ,那就得不偿失了。

观察到所有的 len\leq n ,不妨使用基数排序。

但是这种方法有一定的局限性,比如说广义 \rm SAM 用不了,某些时候操作麻烦等等……

我们也维护了某个点的最长串 len ,统计 \max\limits_u[u.siz<1](u.siz*u.len) 即可。

Code:

这里只提供树形dp版,基排版可以到其他题目里面找。

#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;
}

首先这个翻译非常的假,人话题意:本质不同子串出现次数的平方和

对于 \rm SAM 上的节点,计算\sum\limits_{u}u.siz^2*(u.len-fa.len)即可。

评测记录

题意 : 不断push_back字符,每次统计本质不同子串数。

( 这道题字符集很大,需要使用 std::map 建立后缀自动机 )

上文4.2中,我们讲到 ANS=\sum\limits_{u}(u.len-u.fa.len)

那么每次有 len 变化的时候,维护这个总和就好了。

首先新建 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;即可。

评测记录

• [P3975 [TJOI2015]弦论](https://www.luogu.org/problemnew/show/P3975)

细节比较的多TAT

我们考虑使用类似线段树上二分的办法,在 \rm SAM 上跳(建议结合代码理解)。

已经到达了某个点,我们从 a~z 枚举出边,选定后,当前剩余的 k 要减去字典序比当前构造串小的串的个数。

注意在开始选择路径之前,还得要减去一些东西(详见代码)……

问题就在于减掉多少。设 f[u] 表示从 u 出发能得到的字符串个数。

这很好办, f[u]=从该点出发的路径总条数,这个按照4.2.1dp出来。

开始麻烦了……我们知道一个子串 s 的出现次数={\rm edp}(s)

那么我们就是要统计DAG上 u 的一颗子DAG内, \sum\limits_{path:u\rightarrow v}v.siz

也就是每一个串(路径)的贡献是 : 终点的 |edp| ,即siz。

采用4.3的方法计算siz即可。

那么如何统计呢?这也好办,4.2.1中空串的贡献是1,现在改成siz就可以了。

如何判断无解?这道题同样不计空串,我们要在 f[1] 内把空串的贡献去掉,然后 f[1]<k 即无解(一共没有 k 个满足题意的子串)。

注意其他点空串的贡献是不能去掉的,因为空串表示停止在该点。

评测记录

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

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

回忆 : 自动机某个点表示的串,是指从根到该点的路径构成的所有串。

众所周知,AC自动机的 fail 指针指向的地方,是该节点表示的串的最长后缀,也就是把前面去掉(尽可能少的)一点。

我们注意到 \rm SAM 的fa指针有同样的性质 : 儿子是由父亲在前面加字符产生的,那么父亲就可以视作在儿子前面去掉字符。

我们完全可以把 \rm SAM 理解为把某个串的所有子串建立AC自动机。

这有什么用呢? 来看一下例题吧:

我们把两个串分别称作 S1,S2.

对于 S2 设一个数组为 slen[1...|S2|].

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 - 多串最长公共子串](https://www.luogu.org/problem/SP1812)

类似地,把第一个串当做匹配串,其他的串建立 $\rm SAM$ 

把第一个串在每个 $\rm SAM$ 上跑匹配,$slen$ 对当前匹配长度取$\min$。

最终回答整个 $slen$ 的 $\max$。

代码奇短无比,比SA+单队不知高到哪里去了。

[AC记录](https://www.luogu.org/record/22923336)

## 5.3 [CF235C Cyclical Quest](https://www.luogu.org/problem/CF235C)

题意 : 给出一个文本串和若干询问串,求每个询问串的所有本质不同循环,能够匹配到的次数。

先不考虑本质不同这件事。

循环就是把询问串第一个字符拿去放在最后面。

可以视为,先把目前匹配到的串的第一个字符删掉,然后再加上一个。

如果目前这个串根本没有在文本中完整出现,那么这个删除操作可以忽略。

否则,`len--`,如果删了前面之后 $len$ **不在当前节点区间**($(u.fa.len,u.len]$)里面了就跳 `f`。

(在前面删掉字符?这不就是parent tree跳`f`的性质吗!)

加字符的操作同上。

(~~太有趣了,双端队列?很有出题价值![笑]~~)

最后把匹配到的所有节点 $siz$ 加在一起就好了。

还要考虑去重问题,这也好办 : 如果同一个询问串多次匹配到同一个节点,贡献只算一次,具体可以打标记实现。

```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] 封印

先建立 S 的 \rm SAM ,然后让 T 在上面跑匹配,求出 T 的每个前缀 i 能够匹配的后缀长度 sl[i]。

对于区间 [l,r] 的限制,答案是 \max\limits_{i=l}^r\min(sl[i],i-l+1)。

可以二分答案 mid , 然后 i 必须满足 i-l+1\geq mid 即 i\geq mid+l-1。

若满足这个要求,那么 i+l+1 的约束就可以不考虑了,变成一个区间 \max 问题,可以用 ST 表做到 O(1)。

复杂度 O(n\log n)。[评测记录] ()

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

6. \rm SAM 构建后缀树

广义 \rm SAM 定义 : 给出多个串,求一个能够识别这些串所有子串的自动机。

构造方法奇为暴力 :

每次加入一个串前,把las设为1。

正确性显然(雾)

补记 : 我naive了,Trie树上正牌的广义SAM一点都不会,枯了……

例题 : SP8093 JZPGYZ - Sevenk Love Oimaster

首先对于所有模板串建立广义 \rm SAM ,求出每个点中有多少类模板串的子串,设为siz。

对于匹配串在 \rm SAM 上跳,假如跳到空则输出0,否则输出siz。

怎么求呢? 我们对第 i 个模板串后缀对应的点染上第 i 种颜色,然后可以静态子树数颜色。

附 : CF427D Match & Catch (近乎广义 \rm SAM 模板)

还有一个奇怪的题 : Loj#6071. 「2017 山东一轮集训 Day5」字符串

先考虑单个串怎么做,前面我们讲过了可以\rm parent树,或者自动机DAG路径计数。

对于多个子串拼接的情况,我们无法构建类似\rm parent的强有力的结构,而DAG路径计数更加简单粗暴,只需要满足自动机的基本性质即可。

我们考虑先对每个串单独建立 \rm SAM ,考虑这个DAG的意义,就是从根开始的路径=字符串的每个子串(不重不漏)。

有考虑另一种能跳跃拼接的字符串数据结构 : 子序列自动机。

其做法就是从每个位置'c'的出边向后连接到最近的一个'c'。

那么,我们考虑把这个若干个 \rm SAM·DAG 魔改一下。

如果某个点没有'c'出边,那么连向后面第一个满足要求的的DAG源点的'c'出边。

引用某位大佬的话 :

现在我们建出来的DAG就非常牛逼了,如果发现想走某一条转移边而没有办法走的时候,它会自动跳到下一个字符串上去,我们在这张DAG上求一下路径总数就是答案了。

看起来很有出题价值。

#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

我们发现 \rm parent 树上,父节点的 \rm edp 恰恰是子节点的 \rm edp 求并,这和树上线段树合并太像了!

我们可以考虑使用线段树合并来维护 \rm edp 集合,来干一些神奇的事。

例题 : CF1037H Security

题意 : 给一个文章串S,给出若干文本串T。

截取 S 的一个字串 S2=S[l...r] ,求 S2 的子串中,严格大于 T 的字典序最小的串,如果没有输出-1。

• 我们先考虑没有截取限制,即 S2=S。

那么,有一个显而易见的贪心:

先建立S的 \rm SAM,然后让T在S上面跑匹配,我们假设在T_p$配不上了。

找一个大于当前T_p那个字符的最小字符放在串尾即可。

问题在于可能候选的字符都是小于T_p的,那我们只能退而求其次,退回上一位,再看看有那个位置没有大于T_{p-1}的。

如果退到源点还是没有方案,那么输出-1。

具体的复杂度是O(|S|+26*\sum|T|),那个26远远跑不满。

• 现在考虑截取限制,即 S2=S[l...r]。

如果我们知道 S[l...r] 的 \rm SAM ,我们就可以套用上述贪心了,但是每次重构复杂度显然不对。

还是要先建立 S 的 \rm SAM ,我们称包含任意一个 S[l...r] 子串的点为“好点”。

那么我们发现,加入我们把所有的“不好点”以及相关的边删掉,那么我们就得到了 S[l...r] 的 \rm SAM 。

这玩意虽然不保证点数边数为 O(|S[l...r]|) ,但还是能恰好匹配所有子串的! (一个合法的自动机)

我们考虑设计一个函数,能够判定某个点是否为好点,那样的话就可以实现上述贪心操作了。

如何判断呢?我们采用线段树合并来维护每个点的 \rm edp 集合,具体做法就是在\rm parent树上由下而上合并线段树,空间受得住。注意合并的时候不能销毁儿子的树。

(当然用普通平衡树启发式合并也是可以的,不过代码长,复杂度还多个\log)

我们只要在线段树上区间查询一下 \rm edp 有没有值就好了,区间是 [l+len-1,r] 。这里 len 是目前字符串的长度。

那么复杂度就是O(|S|logn+26*\sum|T|logn),看起来比较险,其实由于数据水是极松的。

Code:

#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;
}

• P4094 [HEOI2016/TJOI2016]字符串

先把原串倒过来,现在问题变成了 [a,b] 的子串在 [c,d] 中匹配的最长后缀。

考虑二分一个 len ,就变成了 O(\log n) 个 [d-len+1,d] 在 [a+len-1,b] 中的存在性问题。

令 c'=d+len-1;a'=a+len-1.

建立 \rm SAM ,跑一个线段树合并求出每个点的 \rm edp。

然后定位包含子串 [c',d] 的那个点,具体方法 : 先找出前缀 d 的对应结束点,然后看 len 在\rm parent树上倍增。

定位到之后,在当前点看一看有没有 \rm edp 在给出的 [a',b] 内,线段树上一个区间查询就好了。

复杂度 O(nlog^2n) ,常数较大。

评测记录

• SP687 REPEATS - Repeats

结论 ： 若 edp 中两两元素最小的差为 g，那么对答案的贡献即为 \left\lfloor\dfrac{len-g}{g}\right\rfloor。

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

9.SAM上树分治

当你要统计前缀对子之间的贡献时,你会发现往往与 lcs(最长公共后缀) 有关。

而这又能转化成关于\rm parent树上LCA的一些信息,那么我们就可以使用有根树分治来统计。

某些时候也可以直接树剖。

• [DS记录]Loj#6198. 谢特 (启发式合并01Trie)

• [DS记录]P5161 WD与数列 (启发式合并线段树)

• [DS记录]P4482 [BJWC2018]Border 的四种求法 (重链剖分)

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

10.技巧大杂烩

10.1 P4081 [USACO17DEC]Standing Out from the Herd

设这些串分别为 S_{1...n} ,那么构造出 S_{[1,i)} 的广义 \rm SAM 。

然后,利用 \rm SAM 与AC自动机的相似性,把 S_{i} 在 S_{[1,i)} 的广义 \rm SAM 上匹配一下,然后得到某个前缀在其他串上的匹配长度(取\max)。

对于 S(i,n] 的的广义 \rm SAM 也进行同样的匹配操作。

最终可以得到每个串的每个后缀在其他串上的最长匹配长度。

最后对于每个串单独建立 \rm SAM 判重。

具体来讲,就是先随意求出每个点的任意一个 \rm edp ,然后贡献就是根据长度和匹配长度比较,大于匹配长度的那部分才是该串独有的,计入贡献。

评测记录

10.2 P4770 [NOI2018]你的名字

题意: 给出一个文本串和若干询问串,求该询问串没有在文本串某个区间中匹配的本质不同子串个数。

首先弱化一下,不考虑那个区间限制。

做法和上一题差不多,先跑个后缀匹配,然后再对询问串建立 \rm SAM 判重就好了。

问题在于现在加上了区间限制,按照套路,先线段树合并弄出 \rm edp 再说。

考虑一下我们匹配的时候究竟在做什么:

• 跑匹配,也就是要知道能不能匹配,以及下一步的出边是什么。

• 读取len,这样才知道究竟匹配了多长。

• 发现没有出边,跳parent树。

我们要借用原有的 \rm SAM 的框架,来做这三件事情。

在匹配的时候,我们直接取整个 \rm SAM 的出边,然后用线段树查询一下目标节点在要求的区间内有没有 \rm edp ,注意这里和当前匹配长度也有关。

注意!失配了之后不能直接跳f,把匹配的长度减一后,还得再试一次,直到该节点的len不对头为止。

怎么读取 len 呢?

考虑到原有 \rm SAM 节点表示的串 : 长度在某个区间内,且 \rm edp 在某某某的所有子串。

现在要求这些子串必须在某个区间内,那么这个长度区间的上界就要对某个东西取\min,因为最长的串前面一部分可能被砍掉了。这会破坏很多(?)性质。

而下界是不会变的,所以比较下界(fa.len)就知道是否对头了。反正出边会检查,正确性是有保障的。

至于跳f这件事,直接在原自动机上跳就好了,可以证明复杂度是正确的(每跳一次匹配长度至少减一),而且不会丢信息。

#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;
}

• 题解 CF1098F 【Ж-function】