SAM
$\text{SAM}$ 是一个十分 $\text{bdd}$ 的数据结构,然鹅我并不能对它下一个清晰(且我能看懂)的定义……
状态
每个点记录了一个原串的子串集合:
$\text{1.}$ 子串出现的末尾位置集合相同.
$\text{2.}$ 子串是某些前缀的连续后缀,即长度为一个连续的区间.
$\text{3.}$ 集合中所有串都是(集合中)最长串的后缀.
$\text{4.}$ 每个点包含的子串集合互不相交.
每个点保存的信息有:
$len$ :该点表示的串的集合中长度的最大值,最小值则 $=len(fa)+1$ .
$fa$ : 绿色的边指向的点, $fa$ 表示的子串集合都为 $p$ 中串的后缀,且长度均小于最短的串.每个点向 $fa$ 连边可以得到一棵树.
$son$ :蓝色的边指向的点, $son[c]$ 表示 $p$ 中的串后面接上字符 $c$ 后的状态.
$siz$ :子串出现的末尾位置 $endpos$ 集合的大小,可通过拓扑排序(易理解)或某种更优美的方法求,有时还可以顺便记下 $dfn$ (拓扑排序后的顺序).
$pos$ :子串出现的末尾位置中的最后一个?(大概)
建立
Luogu3804
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#define pr(p) printf("%lld\n",p)
const int oo=2139063143;
const int N=2010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
x=0; static int p; p=1; static char c; c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
x*=p;
}
struct SAM { int len,fa,son[28],siz; }sam[N<<1]; int tot=1;
#define len(p) sam[p].len
#define fa(p) sam[p].fa
#define son(p) sam[p].son
#define siz(p) sam[p].siz
int pre=1;
void addchar (int c)
{
int f=pre,p=++tot; pre=p;
len(p)=len(f)+1,siz(p)=1;
while (f&&!son(f)[c]) son(f)[c]=p,f=fa(f);
if (!f) { fa(p)=1; return ; }
int x=son(f)[c];
if (len(x)==len(f)+1) { fa(p)=x; return ; }
int y=++tot;
len(y)=len(f)+1,fa(y)=fa(x),fa(x)=fa(p)=y;
memcpy (son(y),son(x),sizeof (son(y)));
while (f&&son(f)[c]==x) son(f)[c]=y,f=fa(f);
}
char s[N];
queue <int> q;
int deg[N];
int main()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
scanf ("%s",s+1);
int n=strlen (s+1);
for (int i=1; i<=n; i++)
addchar (s[i]-'a'+1);
for (int i=1; i<=tot; i++)
++deg[fa(i)];
for (int i=1; i<=tot; i++)
if (!deg[i]) q.push (i);
LL ans=0;
while (q.size ())
{
int u=q.front (); q.pop ();
if (siz(u)> 1) ans=max (ans,1LL*siz(u)*len(u));
siz(fa(u))+=siz(u);
--deg[fa(u)];
if (!deg[fa(u)]) q.push (fa(u));
}
pr(ans);
return 0;
}
简单应用
codevs3160
求两个串的最长公共子串.
对第一个建 $\text{SAM}$ ,再将第二个放在上面沿着 $son$ 边跑,若跑到没有对应的出边了,可以不断跑向 $fa$ ,( $fa$ 是 $p$ 的后缀,而且出现位置更多),直到有对应的出边为止,并对于第二个串的每个前缀都更新一次答案.
int ans=0,cur=1,cnt=0;
for (int i=1; i<=m; i++)
{
int c=t[i]-'a'+1;
while (fa(cur)&&!son(cur)[c]) cur=fa(cur),cnt=len(cur);
if (son(cur)[c]) cur=son(cur)[c],++cnt;
ans=max (ans,cnt);
}
pr(ans);
CF235C
求若干串在另一个长串 $\text{S}$ 中各自作为子串出现的次数,但匹配的方式从完全相等变成了“循环同构”.
首先可将询问串复制一遍粘在后面,但要去掉最后一个字符(避免重复).
利用 $\text{S}$ 的 $\text{SAM}$ 可求出对于询问串的每个前缀的最长匹配长度.
这个长度 $len$ 可能超过了原询问串的长度,此时可以向 $fa$ 跳,直到 $len(fa)$ 比原询问串长,才能保证不漏.因为 $len$ 若比原串长度长,则会少计算一些满足”匹配长度长于原串,却无法达到 $len$ “的串.
int T; sc(T);
for (int kind=1; kind<=T; kind++)
{
scanf ("%s",t+1);
int len=strlen (t+1);
for (int i=len+1; i< len<<1; i++)
t[i]=t[i-len];
int cur=1,cnt=0,ans=0;
for (int i=1; i< len<<1; i++)
{
int c=t[i]-'a'+1;
while (fa(cur)&&!son(cur)[c]) cur=fa(cur),cnt=len(cur);
if (son(cur)[c]) cur=son(cur)[c],++cnt;
if (cnt>=len)
{
while (len(fa(cur))>=len) cur=fa(cur),cnt=len(cur);
if (vis[cur]!=kind) ans+=siz(cur),vis[cur]=kind;
}
}
pr(ans);
}
CF427D
求两个串的最短公共唯一子串(仅在两个串中分别各出现 $\text{1}$ 次).
对 $\text{A}$ 建立 $\text{SAM}$ ,只在 $\text{A}$ 中出现 $\text{1}$ 次的串肯定是 $siz$ 为 $\text{1}$ 的.
将 $\text{B}$ 在 $\text{SAM}$ 上面跑,得到 $\text{B}$ 在每个状态的出现次数 $cnt$,当某个状态的 $cnt=siz=1$ 时,更新答案.
int cur=1,l=0;
for (int i=1; i<=m; i++)
{
int c=t[i]-'a'+1;
while (fa(cur)&&!son(cur)[c]) cur=fa(cur),l=len(cur);
if (son(cur)[c]) cur=son(cur)[c],++l;
if (l>=len(fa(cur))+1) ++cnt[cur];
else ++cnt[fa(cur)];
}
int ans=oo;
for (int i=1; i<=tot; i++)
{
int u=dfn[i];
if (cnt[u]==1&&siz(u)==1) ans=min (ans,len(fa(u))+1);
cnt[fa(u)]+=cnt[u];
}
pr(ans==oo?-1:ans);
广义SAM
多个串建在同一个 $\text{SAM}$ 上.
建立
最智障法
每次插入时 $pre=1$ .
这会导致产生部分废点,不影响正确性,占空间.
不太智障法&标准法
不会.
应用
CF452E
给定 $\text{3}$ 个串,对于每个 $L \in [1, \min(len_A,len_B,len_C)]$ ,求满足 $A[a,a+L-1]=B[b,b+L-1]=C[c,c+L-1]$ 的三元组 $(a,b,c)$ 的数量.
建一个广义 $\text{SAM}$ ,求出对于每个点,分别在 $\text{3}$ 个串中的出现次数,然后相乘,更新该点最短长度的答案,再求一发前缀和即可.
for (int i=0; i< 3; i++)
{
int cur=1;
for (int j=1; j<=l[i]; j++)
cur=son(cur)[s[i][j]-'a'+1],++siz(cur)[i];
}
for (int i=1; i<=tot; i++)
++deg[fa(i)];
for (int i=1; i<=tot; i++)
if (!deg[i]) q.push (i);
while (q.size ())
{
int u=q.front (),f=fa(u); q.pop ();
for (int i=0; i< 3; i++)
siz(f)[i]+=siz(u)[i];
if (!(--deg[f])) q.push (f);
}
for (int i=1; i<=tot; i++)
{
int g=1LL*siz(i)[0]*siz(i)[1]*siz(i)[2]%mod;
(ans[len(fa(i))+1]+=g)%=mod,(ans[len(i)+1]-=g)%=mod;
}
for (int i=1; i<=mi; i++)
{
ans[i]+=ans[i-1];
ans[i]=(ans[i]%mod+mod)%mod;
pr(ans[i]);
}
线段树合并
临时插几句,后面用得到.
有两棵动态开点线段树,要将其对应位置的信息合并,递归进行合并.
应用
Luogu3521
二叉树.可以交换每个点的左右子树.要求前序遍历叶子的逆序对最少.
struct TREE { int ls,rs; LL sum; }t[N*20]; int tot=0;
#define ls(p) t[p].ls
#define rs(p) t[p].rs
#define sum(p) t[p].sum
int update (int p,int w,int l,int r)//单点增加
{
if (!p) p=++tot;
++sum(p);
if (l==r) return p;
int mid=(l+r)>>1;
if (w<=mid) ls(p)=update (ls(p),w,l,mid);
else rs(p)=update (rs(p),w,mid+1,r);
return p;
}
LL ans,an1,an2;
int merge (int x,int y)//合并,an1/2为x/y放在左边的逆序对数量
{
if (!x||!y) return x+y;
sum(x)+=sum(y);
an1+=sum(rs(x))*sum(ls(y));
an2+=sum(ls(x))*sum(rs(y));
ls(x)=merge (ls(x),ls(y));
rs(x)=merge (rs(x),rs(y));
return x;
}
int solve ()
{
int t,p=0; sc(t);
if (!t)
{
int ls,rs;
ls=solve (),rs=solve ();
an1=an2=0;
p=merge (ls,rs);
ans+=min (an1,an2);
}
else p=update (p,t,1,n);
return p;
}
与SAM一起用
用于维护每个点的 $endpos$ 或其它一些什么东西.
栗子
for (int i=1; i<=n; i++)
addchar (s[i]-'a'+1,i),rt[pre]=update (0,i,1,n);
for (int i=1; i<=totsam; i++)
++deg[fa(i)];
for (int i=1; i<=totsam; i++)
if (!deg[i]) q.push (i);
while (q.size ())
{
int u=q.front (),f=fa(u); q.pop ();
if (!f) continue;//!!!!!!
rt[f]=merge (rt[f],rt[u]);
if (!(--deg[f])) q.push (f);
}
CF666E
给定一个串 $S$ 以及一个字符串数组 $T[1..m]$ , $q$ 次询问,每次问 $S$ 的子串 $S[p_l,p_r]$ 在 $T[wl,wr]$ 中的哪个串里的出现次数最多,并输出出现次数.
对 $T$ 建广义 $\text{SAM}$ ,对于每个点,求 $T$ 中的每个串(的子串)在该点中的出现次数,用线段树合并维护.
将查询离线(也有不离线的做法),按照 $wr$ 排序.
把 $S$ 放在 $\text{SAM}$ 上跑,对于每个以 $i$ 结尾的后缀,都可以得到在 $\text{SAM}$ 上的最大匹配长度 $len$ .
(同 $CF235C$ ) $len$ 可能比询问的子串长以至于不能得到最大答案,于是要向 $fa$ 跳,并保证满足 $(p_r-p_l+1)<=len(f)$ ,使用倍增加快向上跳的速度.
跳完后,在当前点的线段树上的 $[wl,wr]$ 查询最大值及位置.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
x=0; static int p; p=1; static char c; c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
x*=p;
}
struct TREE { int ma,ls,rs,we,sum; }tree[N*20]; int totree=0,rt[N];
#define ma(p) tree[p].ma
#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
#define we(p) tree[p].we
#define sum(p) tree[p].sum
int update (int p,int w,int d,int l,int r)
{
if (!p) p=++totree;
if (l==r) { ma(p)+=d,we(p)=l,sum(p)+=d; return p; }
int mid=(l+r)>>1;
if (w<=mid) ls(p)=update (ls(p),w,d,l,mid);
else rs(p)=update (rs(p),w,d,mid+1,r);
ma(p)=max (ma(ls(p)),ma(rs(p)));
we(p)=(ma(p)==ma(ls(p)))?we(ls(p)):we(rs(p));
sum(p)=sum(ls(p))+sum(rs(p));
return p;
}
int merge (int x,int y,int l,int r)
{
if (!x||!y) return x+y;
int z=++totree,mid=(l+r)>>1;
ls(z)=merge (ls(x),ls(y),l,mid);
rs(z)=merge (rs(x),rs(y),mid+1,r);
if (l==r) { ma(z)=ma(x)+ma(y),we(z)=l,sum(z)=ma(z); }
else
{
ma(z)=max (ma(ls(z)),ma(rs(z)));
we(z)=(ma(z)==ma(ls(z)))?we(ls(z)):we(rs(z));
sum(z)=sum(ls(z))+sum(rs(z));
}
return z;
}
#define fi first
#define se second
pair <int,int> query (int p,int l,int r,int L,int R)
{
if (l<=L&&R<=r) return make_pair (ma(p),we(p));
int mid=(L+R)>>1; pair <int,int> ans,lin; ans.fi=ans.se=0;
if (l<=mid) ans=query (ls(p),l,r,L,mid);
if (r> mid) lin=query (rs(p),l,r,mid+1,R);
if (lin.fi> ans.fi) ans=lin;
return ans;
}
struct SAM { int len,fa,son[28],siz; }sam[N<<1]; int totsam=1;
#define len(p) sam[p].len
#define fa(p) sam[p].fa
#define son(p) sam[p].son
#define siz(p) sam[p].siz
int pre=1;
void addchar (int c)
{
int f=pre,p=++totsam; pre=p;
len(p)=len(f)+1,siz(p)=1;
while (f&&!son(f)[c]) son(f)[c]=p,f=fa(f);
if (!f) { fa(p)=1; return ; }
int x=son(f)[c];
if (len(x)==len(f)+1) { fa(p)=x; return ; }
int y=++totsam;
len(y)=len(f)+1,fa(y)=fa(x),fa(x)=fa(p)=y;
memcpy (son(y),son(x),sizeof (son(y)));
while (f&&son(f)[c]==x) son(f)[c]=y,f=fa(f);
}
char s[N],sb[N];
vector <char> t[N];
int len[N];
queue <int> q;
int deg[N],dfn[N],fa[N][20];
struct LY { int wl,wr,pl,pr,id; }p[N];
bool ly (LY A,LY B) { return A.pr< B.pr; }
pair <int,int> ans[N];
int main()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
scanf ("%s",s+1);
len[0]=strlen (s+1);
int n; sc(n);
for (int i=1; i<=n; i++)
{
scanf ("%s",sb+1);
len[i]=strlen (sb+1);
pre=1;
for (int j=1; j<=len[i]; j++)
addchar (sb[j]-'a'+1),t[i].push_back (sb[j]);
}
int m; sc(m);
for (int i=1; i<=m; i++)
sc(p[i].wl),sc(p[i].wr),sc(p[i].pl),sc(p[i].pr),p[i].id=i;
for (int i=1; i<=n; i++)
for (int j=0,cur=1; j< len[i]; j++)
{
cur=son(cur)[t[i][j]-'a'+1];
rt[cur]=update (rt[cur],i,1,1,n);
}
for (int i=1; i<=totsam; i++)
++deg[fa(i)];
for (int i=1; i<=totsam; i++)
if (!deg[i]) q.push (i);
while (q.size ())
{
int u=q.front (),f=fa(u); q.pop (); dfn[++dfn[0]]=u;
if (!f) continue;
fa[u][0]=f;
rt[f]=merge (rt[f],rt[u],1,n);
if (!(--deg[f])) q.push (f);
}
for (int i=totsam; i>=1; i--)
{
int u=dfn[i];
for (int j=1; j<=18; j++)
fa[u][j]=fa[fa[u][j-1]][j-1];
}
sort (p+1,p+m+1,ly);
int cur=1,cnt=0,ask=1;
for (int i=1; i<=len[0]; i++)
{
int c=s[i]-'a'+1;
while (fa(cur)&&!son(cur)[c]) cur=fa(cur),cnt=len(cur);
if (son(cur)[c]) cur=son(cur)[c],++cnt;
while (p[ask].pr==i)
{
int l=p[ask].pr-p[ask].pl+1,sb=p[ask].id;
if (cnt< l) { ans[sb].se=p[ask].wl,++ask; continue; }
int u=cur;
for (int j=18; j>=0; j--)
{
int f=fa[u][j];
if (l<=len(f)) u=f;
}
ans[sb]=query (rt[u],p[ask].wl,p[ask].wr,1,n);
if (ans[sb].fi==0) ans[sb].se=p[ask].wl;
++ask;
}
}
for (int i=1; i<=m; i++)
printf ("%d %d\n",ans[i].se,ans[i].fi);
return 0;
}
CF700E
给定字符串 $S$,定义一个字符串序列 $a[1…k]$ ,求最大的 $k$ ,满足性质: $a[i]$ 在 $a[i-1] (i>=2)$ 中出现至少两次(位置可重叠).
首先对 $S$ 建 $\text{SAM}$ ,线段树合并求 $endpos$ 集合.
设 $F[u]$ 为从根节点到 $u$ 点的最大的 $k$ 是多少.
由于每个点只从其 $fa$ 贡献而来,而 $fa$ 可能无法对该点进行贡献,于是还要记录 $top[u]$ 表示从根节点到 $u$ 点的路径上的最后一个有贡献的点(即 $top[u]$ 以下到 $fa$ 都没有贡献).
int ans=1;
for (int i=totsam-1; i>=1; i--)
{
int u=dfn[i],f=fa(u);
if (f==1) { F[u]=1,top[u]=u; continue; }
bool g=query (rt[top[f]],pos(u)-(len(u)-len(top[f])),pos(u)-1,1,n);
if (g) F[u]=F[f]+1,top[u]=u;
else F[u]=F[f],top[u]=top[f];
ans=max (ans,F[u]);
}
Luogu4770
给定一个串 $S$ , $n$ 个询问,每个询问给出一个串 $T$ ,一个区间 $[l,r]$ 对应 $S$ 的一个子串 $G$,求 $T$ 的满足没有在 $G$ 中出现过的本质不同子串数量.
首先转化成求在 $G$ 中出现过的(不合法).
考虑只有 $l=1,r=| S |$ 的询问,对 $S$ 建 $\text{SAM}$ 将 $T$ 放在上面跑,此时 $T$ 的每个前缀对答案的贡献是前缀长度-匹配长度.
去重就再对 $T$ 建立 $\text{SAM}$ 即可.
再考虑 $l,r$ 任意的情况,先对 $S$ 建 $\text{SAM}+$ 线段树合并求 $endpos$ 集合.
于是 $T$ 在 $S.\text{SAM}$ 上跑的时候,判断是否可以前往 $son[c]$ 的标准不再仅仅是存在 $son[c]$ ,更需要 $son[c]$ 的 $endpos$ 集合中存在 $[l+cnt,r]$ 中任意一个位置( $cnt$ 为已匹配长度).
再记录 $T$ 的每个前缀能够匹配的长度 $lim$ ,剩下的和普通匹配差不多.
最后统计答案,对于每个在 $T.\text{SAM}$ 上的点,统计答案即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
#include <cmath>
#define pr(p) printf("%lld\n",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
x=0; static int p; p=1; static char c; c=getchar();
while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
x*=p;
}
struct TREE { int ls,rs; }tree[N*20]; int totree=0,rt[N];
#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
int update (int p,int w,int l,int r)
{
if (!w) return 0;
if (!p) p=++totree;
if (l==r) return p;
int mid=(l+r)>>1;
if (w<=mid) ls(p)=update (ls(p),w,l,mid);
else rs(p)=update (rs(p),w,mid+1,r);
return p;
}
int merge (int x,int y)
{
if (!x||!y) return x+y;
int z=++totree;
ls(z)=merge (ls(x),ls(y));
rs(z)=merge (rs(x),rs(y));
return z;
}
bool query (int p,int l,int r,int L,int R)
{
if (!p) return 0;
if (l<=L&&R<=r) return 1;
int mid=(L+R)>>1;
if (l<=mid&&query (ls(p),l,r,L,mid)) return 1;
if (r> mid&&query (rs(p),l,r,mid+1,R)) return 1;
return 0;
}
int n,m;
struct SAM { int len,fa,son[28],pos; }sam[N<<1]; int totsam=1;
#define len(p) sam[p].len
#define fa(p) sam[p].fa
#define son(p) sam[p].son
#define pos(p) sam[p].pos
int pre=1;
void addchar (int c,int pos)
{
int f=pre,p=++totsam; pre=p;
len(p)=len(f)+1,pos(p)=pos;
while (f&&!son(f)[c]) son(f)[c]=p,f=fa(f);
if (!f) { fa(p)=1; return ; }
int x=son(f)[c];
if (len(x)==len(f)+1) { fa(p)=x; return ; }
int y=++totsam; pos(y)=pos(x);
len(y)=len(f)+1,fa(y)=fa(x),fa(x)=fa(p)=y;
memcpy (son(y),son(x),sizeof (son(y)));
while (f&&son(f)[c]==x) son(f)[c]=y,f=fa(f);
}
struct sbSAM { int len,fa,son[28],sbsiz,sbpos; }sbbb[N<<1]; int sbtotsam;
#define sblen(p) sbbb[p].len
#define sbfa(p) sbbb[p].fa
#define sbson(p) sbbb[p].son
#define sbsiz(p) sbbb[p].sbsiz
#define sbpos(p) sbbb[p].sbpos
int sbpre;
void sbaddchar (int c,int pos)
{
int f=sbpre,p=++sbtotsam; sbpre=p;
sblen(p)=sblen(f)+1,sbsiz(p)=1,sbpos(p)=pos;
while (f&&!sbson(f)[c]) sbson(f)[c]=p,f=sbfa(f);
if (!f) { sbfa(p)=1; return ; }
int x=sbson(f)[c];
if (sblen(x)==sblen(f)+1) { sbfa(p)=x; return ; }
int y=++sbtotsam; sbpos(y)=sbpos(x);
sblen(y)=sblen(f)+1,sbfa(y)=sbfa(x),sbfa(x)=sbfa(p)=y;
memcpy (sbson(y),sbson(x),sizeof (sbson(y)));
while (f&&sbson(f)[c]==x) sbson(f)[c]=y,f=sbfa(f);
}
int lim[N];
void clean ()
{
for (int i=1; i<=sbtotsam; i++)
{
sblen(i)=sbfa(i)=sbsiz(i)=0;
memset (sbson(i),0,sizeof (sbson(i)));
lim[i]=0;
}
sbtotsam=sbpre=1;
}
char s[N],t[N];
queue <int> q;
int deg[N];
void getbzbt (int len)
{
sbtotsam=sbpre=1;
for (int i=1; i<=len; i++)
sbaddchar (t[i]-'a'+1,i);
}
int main()
{
//freopen (".in","r",stdin);
//freopen (".out","w",stdout);
scanf ("%s",s+1);
n=strlen (s+1);
for (int i=1; i<=n; i++)
addchar (s[i]-'a'+1,i),rt[pre]=update (0,i,1,n);
for (int i=1; i<=totsam; i++)
++deg[fa(i)];
for (int i=1; i<=totsam; i++)
if (!deg[i]) q.push (i);
while (q.size ())
{
int u=q.front (),f=fa(u); q.pop ();
if (!f) continue;//!!!!!!
rt[f]=merge (rt[f],rt[u]);
if (!(--deg[f])) q.push (f);
}
sc(m);
while (m--)
{
scanf ("%s",t+1);
int len=strlen (t+1),l,r;
getbzbt (len);
sc(l),sc(r);
int cur=1,cnt=0;
for (int i=1; i<=len; i++)
{
int c=t[i]-'a'+1;
while (1)
{
int sb=query (rt[son(cur)[c]],l+cnt,r,1,n);
if (!sb)
{
if (!cnt) break;
--cnt;
if (cnt==len(fa(cur))) cur=fa(cur);
}
else { cur=son(cur)[c],++cnt; break; }
}
lim[i]=cnt;
}
LL ans=0;
for (int i=2; i<=sbtotsam; i++)
ans+=max (0,sblen(i)-max (sblen(sbfa(i)),lim[sbpos(i)]));
pr(ans);
clean ();
}
return 0;
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：SAM”