SAM 做题笔记
\(\newcommand\oper\operatorname\)
\(\text{By DaiRuiChen007}\)
0. 前言
符号表达及约定
- \(\oper{SAM}(S)\)：表示对 \(S\) 建立的 SAM
- \(\oper{SAM}(S_1,S_2,\dots,S_n)\)：表示对 \(S_1,S_2,\dots,S_n\) 建立的广义 SAM
- \(\oper{null}\)：在字符串匹配过程中匹配串不为 \(S\) 子串后跳转至的节点，实现时用 \(0\) 表示
- \(\oper{root}\)：SAM 匹配的起始节点，实现时用 \(1\) 表示
- \(\delta(p,ch)\)：SAM 中 \(p\) 状态读入 \(ch\) 后转移到的后继状态
- \(\oper{endpos}(p)\)：表示后缀自动机上 \(p\) 节点对应字符串的 \(\oper{endpos}\) 集合
- \(\oper{link}(p)\)：表示后缀自动机上 \(p\) 节点的后缀链接
- \(\oper{len}(p)/\oper{maxlen}(p)\)：表示后缀自动机上 \(p\) 节点对应字符串集合中长度最长的一个
- \(\oper{minlen}(p)\)：表示后缀自动机上的 \(p\) 节点对应字符串集合中长度最短的一个，当 \(p\ne \oper{root}\) 时，满足 \(\oper{minlen}(p)=\oper{maxlen}(\oper{link}(p))+1\)
- \(\oper{pos}(T)\)：用 \(T\) 在 SAM 中匹配后得到的终止节点，约定 \(\oper{pos}(\varnothing)=\oper{root}\)
- \(\oper{suffix}(r)\)：表示把长度为 \(r\) 的前缀在 SAM 中匹配后得到的终止节点，即 \(\oper{suffix}(r)=\oper{pos}(S[1\dots r])\)
- \(\oper{cnt}(p)\)：SAM 上 \(p\) 节点对应的字符串在 \(S\) 中的出现次数，\(\oper{cnt}(p)=|\oper{endpos}(p)|\)
推荐阅读
- [22] - 区间本质不同子串个数
技巧总结
- 线段树合并维护节点信息（\(\oper{endpos}(p)\)，\(\oper{cnt}(p)\)）：[7]、[16]、[19]、[20]、[23]
- LCT 维护 Parent Tree 信息：[14]、[22]
- 维护区间子串信息可以转成 \(\oper{endpos}\) 上的区间查询：[19]、[20]
- Parent Tree 上倍增求 \(\oper{pos}(S[l\dots r])\)：[20]、[23]
1. [P3804] - 【模板】后缀自动机
后缀自动机模板，注意到 \(r\in\oper{endpos}(p)\) 实际上等价于 \(\oper{suffix}(r)\) 在 Parent Tree 中在 \(p\) 的子树内
因此 \(\oper{cnt}(p)\) 只需要数 \(p\) 在 Parent Tree 的子树中有多少 \(\oper{suffix}(r)\)，在构造 SAM 的过程标记所有 \(\oper{suffix}(r)\)，最后建出 Parent Tree 自下向上转移子树和即可
时间复杂度 \(\Theta(|S|)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+1;
struct node {
int link,len;
map <char,int> son;
node() { son.clear(),link=0,len=0; }
} st[MAXN<<1];
int siz=1,lst=1;
inline int insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p!=0&&st[p].son[c]==0) {
st[p].son[c]=cur;
p=st[p].link;
}
if(p==0) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[p].len+1==st[q].len) st[cur].link=q;
else {
int clone=++siz;
st[clone]=st[q],st[clone].len=st[p].len+1;
st[cur].link=st[q].link=clone;
while(p!=0&&st[p].son[c]==q) {
st[p].son[c]=clone;
p=st[p].link;
}
}
}
lst=cur;
return cur;
}
char str[MAXN];
vector <int> G[MAXN<<1];
int cnt[MAXN<<1],ans=0;
inline void dfs(int p) {
for(int v:G[p]) {
dfs(v);
cnt[p]+=cnt[v];
}
if(cnt[p]>1) ans=max(ans,cnt[p]*st[p].len);
}
signed main() {
scanf("%s",str+1);
int n=strlen(str+1);
for(int i=1;i<=n;++i) ++cnt[insert(str[i])];
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
dfs(1);
printf("%lld\n",ans);
return 0;
}
2. [P2408] - 不同子串个数
注意到根据 SAM 的性质，若 \(S\) 的两个子串 \(S_1,S_2\) 满足 \(\oper{pos}(S_1)\ne\oper{pos}(S_2)\)，显然有 \(S_1\ne S_2\)，因此只需要对每个节点的贡献求和，显然每个节点对应的所有字符串和他们的长度构成双射，因此每个节点的贡献就是 \(\oper{maxlen}(p)-\oper{minlen}(p)+1\)，直接求和即可
时间复杂度 \(\Theta(n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur;
}
char str[MAXN];
signed main() {
int n;
scanf("%lld%s",&n,str+1);
for(int i=1;i<=n;++i) insert(str[i]);
int ans=0;
for(int i=2;i<=siz;++i) ans+=st[i].len-st[st[i].link].len;
printf("%lld\n",ans);
return 0;
}
3. [SPOJ1811] - LCS
先建出 \(\oper{SAM}(S)\)，然后贪心地用 \(T\) 在 SAM 上匹配，假设 \(T[1\dots r]\) 匹配到节点 \(p\)，若 \(\delta(p,T_{r+1})\ne\oper{null}\) 那么则直接匹配到 \(\delta(p,T_{r+1})\) 否则在后缀树上不断上行，令 \(p\gets \oper{link}(p)\)，等价于舍弃 \(T[1\dots r+1]\) 的某个前缀，转而去匹配某个后缀 \(T[l+1\dots r]\)
时间复杂度 \(\Theta(|S|+|T|)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2.5e5+1;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur;
}
char S[MAXN],T[MAXN];
signed main() {
scanf("%s%s",S+1,T+1);
int n=strlen(S+1),m=strlen(T+1);
for(int i=1;i<=n;++i) insert(S[i]);
int ans=0;
for(int i=1,p=1,len=0;i<=m;++i) {
auto match=[&](char c) -> void {
if(st[p].son.find(c)!=st[p].son.end()) {
++len,p=st[p].son[c];
} else {
while(p&&st[p].son.find(c)==st[p].son.end()) p=st[p].link;
if(!p) p=1,len=0;
else len=st[p].len+1,p=st[p].son[c];
}
};
match(T[i]);
ans=max(ans,len);
}
printf("%d\n",ans);
return 0;
}
4. [P4070] - 生成魔咒
考虑每次增加一个新字符对答案的贡献，注意到构建 SAM 的过程中克隆节点操作本质上只是把一个节点的字符串按 \(\le \oper{len}(p)+1\) 和 \(>\oper{len(p)}+1\) 分成两类并分裂成两个节点，并不会增加本质自不同子串的计数
因此每个新增字符 \(S_i\) 的贡献即为 \(\oper{maxlen}(\oper{suffix}(i))-\oper{minlen}(\oper{suffix}(i))+1\)，在插入的过程中可以直接统计
时间复杂度 \(\Theta(n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
struct node {
int link,len;
map <int,int> son;
node() { link=0,len=0; son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1,ans=0;
inline void insert(int c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
ans+=st[cur].len-st[st[cur].link].len;
lst=cur;
}
signed main() {
int n;
scanf("%lld",&n);
for(int i=1;i<=n;++i) {
int c;
scanf("%lld",&c);
insert(c);
printf("%lld\n",ans);
}
return 0;
}
5. [P5341] - 甲苯先生和大中锋的字符串
在 Parent Tree 上转移出每个节点的 \(\oper{cnt}(p)\)，对于 \(\oper{cnt}(p)=k\) 的节点进行处理：显然 \(p\) 对于所有 \(L\in[\oper{minlen}(p),\oper{maxlen}(p)]\) 的长度 \(L\) 有 \(1\) 的贡献，因此每个 \(p\) 的贡献可以转化为区间加操作，用差分维护最后扫描统计答案即可
时间复杂度 \(\Theta(n)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
struct node {
int len,link;
map <char,int> son;
node() { son.clear(),len=0,link=0; }
} st[MAXN<<1];
int siz=1,lst=1;
int cnt[MAXN<<1];
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur,++cnt[cur];
}
vector <int> G[MAXN<<1];
int d[MAXN];
char s[MAXN];
inline void solve() {
int n,k;
scanf("%s%d",s+1,&k);
n=strlen(s+1),lst=1,siz=1;
for(int i=1;i<=n;++i) insert(s[i]);
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
cnt[p]+=cnt[v];
}
if(cnt[p]==k) {
++d[st[st[p].link].len+1];
if(st[p].len<n) --d[st[p].len+1];
}
};
dfs(dfs,1);
int ans=0;
for(int i=1;i<=n;++i) {
d[i]+=d[i-1];
if(d[i]>=d[ans]) ans=i;
}
if(!d[ans]) puts("-1");
else printf("%d\n",ans);
for(int i=1;i<=siz;++i) st[i]=node(),G[i].clear(),cnt[i]=0;
for(int i=1;i<=n;++i) d[i]=0;
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
6. [CF802I] - Fake News
直接对每个节点统计出 \(\oper{cnt}(p)\)，每个节点的贡献就是 \((\oper{maxlen}(p)-\oper{minlen}(p)+1)\times\oper{cnt}(p)^2\)，求和即可
时间复杂度 \(\Theta(|S|)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
struct node {
int len,link;
map <char,int> son;
node() { son.clear(),len=0,link=0; }
} st[MAXN<<1];
int siz=1,lst=1;
int cnt[MAXN<<1];
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur,++cnt[cur];
}
vector <int> G[MAXN<<1];
char s[MAXN];
inline void solve() {
int n,ans=0;
scanf("%s",s+1);
n=strlen(s+1),lst=1,siz=1;
for(int i=1;i<=n;++i) insert(s[i]);
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
cnt[p]+=cnt[v];
}
ans+=cnt[p]*cnt[p]*(st[p].len-st[st[p].link].len);
};
dfs(dfs,1);
printf("%lld\n",ans);
for(int i=1;i<=siz;++i) st[i]=node(),G[i].clear(),cnt[i]=0;
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
7. [SPOJ8093] - Sevenk Love Oimaster
首先对于模板串建立广义 SAM，此时我们需要维护广义 SAM 上的每个节点在哪些字符串中出现过，这里引入一个常用 Trick：
Trick #1：
需要快速维护 SAM 上每个字符串的某些信息时，可以考虑用线段树记录，然后在 Parent Tree 上从下往上用线段树合并维护信息
一般来说，在正常 SAM 上我们一般用线段树合并显式地维护 \(\oper{endpos}(p)\)，而在广义 SAM 上我们一般用线段树合并对某个节点维护其所有的 \(\oper{cnt}(p)\)（即对应字符串实际在哪些模板串中出现过）
本题显然只需要用线段树合并维护每个节点对应的字符串是否在某个模式串中出现过，在叶子结点上用或运算合并即可
每次询问串 \(T\) 直接暴力找到 \(\oper{pos}(T)\) 回答即可
时间复杂度 \(\Theta(S\log S+T)\)，其中 \(S\) 表示模式串长度和，\(T\) 表示询问串长度和
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
class SegmentTree {
private:
int siz;
struct node {
int sum,ls,rs;
node() { sum=0,ls=rs=0; }
} tree[MAXN*50];
inline void pushup(int pos) {
tree[pos].sum=tree[tree[pos].ls].sum+tree[tree[pos].rs].sum;
}
public:
SegmentTree() { siz=0; }
inline void Insert(int u,int l,int r,int &pos) {
if(!pos) pos=++siz;
if(l==r) { tree[pos].sum|=1; return ; }
int mid=(l+r)>>1;
if(u<=mid) Insert(u,l,mid,tree[pos].ls);
if(mid<u) Insert(u,mid+1,r,tree[pos].rs);
pushup(pos);
}
inline void Merge(int l,int r,int &des,int src) {
if(!des||!src) { des+=src; return ; }
if(l==r) { tree[des].sum|=tree[src].sum; return ; }
int mid=(l+r)>>1;
Merge(l,mid,tree[des].ls,tree[src].ls);
Merge(mid+1,r,tree[des].rs,tree[src].rs);
pushup(des);
}
inline int Query(int pos) { return tree[pos].sum; }
} T;
int root[MAXN<<1],ans[MAXN<<1];
int n,q;
class ExSAM {
public:
struct node {
int len,link;
map <char,int> son;
node() { len=0,link=0,son.clear(); }
} st[MAXN<<1];
int siz;
ExSAM() { siz=1; }
private:
inline int newch(int lst,char c) {
int cur=st[lst].son[c];
if(st[cur].len!=0) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].link=st[q].link,st[r].len=st[p].len+1;
for(auto e:st[q].son) if(st[e.second].len) st[r].son[e.first]=e.second;
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
inline void insert(int id,const string &str) {
int pos=1;
for(auto c:str) {
if(st[pos].son.find(c)==st[pos].son.end()) st[pos].son[c]=++siz;
pos=st[pos].son[c];
T.Insert(id,1,n,root[pos]);
}
}
inline void build() {
queue <pair<char,int> > q;
for(auto e:st[1].son) q.push(make_pair(e.first,1));
while(!q.empty()) {
int lst=newch(q.front().second,q.front().first);
q.pop();
for(auto e:st[lst].son) q.push(make_pair(e.first,lst));
}
}
vector <int> G[MAXN<<1];
inline void merge() {
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
T.Merge(1,n,root[p],root[v]);
}
ans[p]=T.Query(root[p]);
};
dfs(dfs,1);
}
inline int query(const string &str) {
int pos=1;
for(auto c:str) {
if(st[pos].son.find(c)==st[pos].son.end()) return 0;
pos=st[pos].son[c];
}
return ans[pos];
}
} SAM;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>q;
for(int i=1;i<=n;++i) {
string str;
cin>>str;
SAM.insert(i,str);
}
SAM.build(),SAM.merge();
while(q--) {
string str;
cin>>str;
cout<<SAM.query(str)<<"\n";
}
return 0;
}
8. [P3975] - 弦论
先考虑一个经典的套路，在 SAM 上通过 \(\delta\) 边匹配，显然只需要计算出 \(dp_p\) 表示 \(p\) 节点向后拓展的字符串数量，就可以通过一遍 dfs 求出答案
当 \(t=0\) 时，\(dp_p\) 等价于 SAM 上一条有向路径，直接在 SAM 对应的 DAG 上拓扑排序转移即可
当 \(t=1\) 时，\(dp_p\) 依然可以对其所有 SAM 上的后继求和，而 \(p\) 本身节点对 \(dp_p\) 的贡献会从 \(1\) 变成 \(\oper{cnt}(p)\)，先用 Parent Tree 预处理一遍即可
时间复杂度 \(\Theta(|S|)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
int cnt[MAXN<<1],sz[MAXN<<1],dp[MAXN<<1];
vector <int> G[MAXN<<1];
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur,++cnt[cur];
}
char s[MAXN];
bool vis[MAXN<<1];
signed main() {
int n,t,k;
scanf("%s%d%d",s+1,&t,&k);
n=strlen(s+1);
for(int i=1;i<=n;++i) insert(s[i]);
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs1=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
cnt[p]+=cnt[v];
}
sz[p]=t?cnt[p]:1;
};
dfs1(dfs1,1),sz[1]=0;
auto dfs2=[&](auto self,int p) -> int {
if(vis[p]) return dp[p];
dp[p]=sz[p];
for(auto e:st[p].son) dp[p]+=self(self,e.second);
vis[p]=true;
return dp[p];
};
dfs2(dfs2,1);
if(dp[1]<k) puts("-1");
else {
string str="";
auto print=[&](auto self,int p) -> void {
if(k<=sz[p]) return ;
k-=sz[p];
for(auto e:st[p].son) {
int v=e.second;
if(dp[v]<k) k-=dp[v];
else {
str.push_back(e.first);
self(self,v); break;
}
}
};
print(print,1);
cout<<str<<"\n";
}
return 0;
}
9. [P6640] - 封印
类比 [3] 的做法，先对 \(T\) 建立 SAM，然后用 \(S\) 在 SAM 上贪心匹配，记录 \(match_i\) 表示 \(S[1\dots i]\) 与 \(T\) 的最长匹配后缀
那么一次查询等价于求 \(\max_{i=l}^r\{\min(i-l+1,match_i)\}\)，考虑二分，当我们判断答案是否 \(\ge k\) 时，我们只需要对所有 \(i-l+1\ge k\) 的 \(i\) 判断 \(match_i\ge k\) 是否存在即可，等价于判断 \(\max_{i=l+k-1}^r\{match_i\}\ge k\) 是否成立，用 ST 表维护 \(match_i\) 的 RMQ 即可完成判定
时间复杂度 \(\Theta((|S|+q)\log|S|)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur;
}
int match[MAXN],f[20][MAXN];
inline int bit(int x) { return 1<<x; }
inline int qmax(int l,int r) {
int k=__lg(r-l+1);
return max(f[k][l],f[k][r-bit(k)+1]);
}
char s[MAXN],t[MAXN];
signed main() {
scanf("%s%s",s+1,t+1);
int n=strlen(s+1),m=strlen(t+1);
for(int i=1;i<=m;++i) insert(t[i]);
for(int i=1,len=0,p=1;i<=n;++i) {
auto add=[&](char c) -> void {
if(st[p].son.find(c)!=st[p].son.end()) ++len,p=st[p].son[c];
else {
while(p&&st[p].son.find(c)==st[p].son.end()) p=st[p].link;
if(!p) len=0,p=1;
else len=st[p].len+1,p=st[p].son[c];
}
};
add(s[i]),match[i]=len;
}
for(int i=1;i<=n;++i) f[0][i]=match[i];
for(int k=1;k<20;++k) {
for(int i=1;i+bit(k-1)<=n;++i) {
f[k][i]=max(f[k-1][i],f[k-1][i+bit(k-1)]);
}
}
int q;
scanf("%d",&q);
while(q--) {
int l,r;
scanf("%d%d",&l,&r);
int bl=0,br=r-l+1,res=0;
while(bl<=br) {
int mid=(bl+br)>>1;
auto check=[&](int x) -> bool { return qmax(x+l-1,r)>=x; };
if(check(mid)) res=mid,bl=mid+1;
else br=mid-1;
}
printf("%d\n",res);
}
return 0;
}
10. [P3346] - 诸神眷顾的幻想乡
注意到树上的每条有向路径都可以表示成树上一条叶子到叶子的有向路径的子串，因此以每个叶子为根，将对应的字符串插入广义 SAM 中，用和正常的 SAM 相同的方法维护本质不同子串数即可
注意到广义 SAM 提前插的过程是用 Trie 维护的，因此插入一棵树时用类似 Trie 结构的方式插入即可
时间复杂度 \(\Theta(nw)\)，其中 \(w\) 表示树的叶子数量
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
class ExSAM {
public:
struct node {
int len,link;
map <int,int> son;
node() { len=0,link=0; son.clear(); }
} st[MAXN*40];
int siz; ExSAM() { siz=1; }
private:
inline int newch(int lst,int c) {
int cur=st[lst].son[c];
if(st[cur].len) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].len=st[p].len+1,st[r].link=st[q].link;
for(auto e:st[q].son) if(st[e.second].len) st[r].son.insert(e);
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
inline void build() {
queue <pair<int,int> > Q;
for(auto e:st[1].son) Q.push(make_pair(1,e.first));
while(!Q.empty()) {
int lst=newch(Q.front().first,Q.front().second);
Q.pop();
for(auto e:st[lst].son) Q.push(make_pair(lst,e.first));
}
}
inline int solve() {
int ret=0;
for(int i=1;i<=siz;++i) ret+=st[i].len-st[st[i].link].len;;
return ret;
}
} SAM;
int a[MAXN];
vector <int> G[MAXN];
signed main() {
int n,c;
scanf("%lld%lld",&n,&c);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
for(int i=1;i<n;++i) {
int u,v;
scanf("%lld%lld",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;++i) {
if((int)G[i].size()>1) continue;
auto dfs=[&](auto self,int pos,int p,int f) -> void {
if(SAM.st[pos].son.find(a[p])==SAM.st[pos].son.end()) {
SAM.st[pos].son[a[p]]=++SAM.siz;
}
pos=SAM.st[pos].son[a[p]];
for(int v:G[p]) if(v!=f) self(self,pos,v,p);
};
dfs(dfs,1,i,0);
}
SAM.build();
printf("%lld\n",SAM.solve());
return 0;
}
11. [CF427D] - Match & Catch
建立 \(\oper{SAM}(S_1,S_2)\)，在 Parent Tree 上转移求出 \(p\) 对应的串在 \(S_1\) 和 \(S_2\) 中分别的出现次数 \(\oper{cnt}_1(p),\oper{cnt}_2(p)\)，找到所有 \(\oper{cnt}_1(p)=1\) 并且 \(\oper{cnt}_2(p)=1\) 的 \(p\)，用 \(\oper{minlen}(p)\) 更新答案即可
时间复杂度 \(\Theta(|S_1|+|S_2|)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5001;
class ExSAM {
public:
struct node {
int len,link;
map <char,int> son;
node() { len=0,link=0; son.clear(); }
} st[MAXN<<2];
int siz; ExSAM() { siz=1; }
private:
inline int newch(int lst,char c) {
int cur=st[lst].son[c];
if(st[cur].len) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].link=st[q].link,st[r].len=st[p].len+1;
for(auto e:st[q].son) if(st[e.second].len) st[r].son.insert(e);
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
vector <int> G[MAXN<<2];
int cnt[MAXN<<2][2];
inline void insert(int id,const string &str) {
int pos=1;
for(auto c:str) {
if(st[pos].son.find(c)==st[pos].son.end()) st[pos].son[c]=++siz;
pos=st[pos].son[c];
++cnt[pos][id];
}
}
inline void build() {
queue <pair<int,char> > Q;
for(auto e:st[1].son) Q.push(make_pair(1,e.first));
while(!Q.empty()) {
int lst=newch(Q.front().first,Q.front().second);
Q.pop();
for(auto e:st[lst].son) Q.push(make_pair(lst,e.first));
}
}
inline int solve() {
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
cnt[p][0]+=cnt[v][0];
cnt[p][1]+=cnt[v][1];
}
};
dfs(dfs,1);
int ret=MAXN;
for(int i=2;i<=siz;++i) if(cnt[i][0]==1&&cnt[i][1]==1) ret=min(ret,st[st[i].link].len+1);
return (ret==MAXN)?-1:ret;
}
} SAM;
signed main() {
string S,T;
cin>>S>>T;
SAM.insert(0,S),SAM.insert(1,T);
SAM.build();
cout<<SAM.solve()<<"\n";
return 0;
}
12. [CF452E] - Three strings
建立 \(\oper{SAM}(A,B,C)\)，Parent Tree 上统计每个节点 \(p\) 对应的字符串在 \(A,B,C\) 中分别的出现次数 \(\oper{cnt}_A(p),\oper{cnt}_B(p),\oper{cnt}_C(p)\)，用 \(\oper{cnt}_A(p)\times\oper{cnt}_B(p)\times\oper{cnt}_C(p)\) 更新 \([\oper{minlen}(p),\oper{maxlen}(p)]\) 的答案，用差分维护即可
时间复杂度 \(\Theta(|A|+|B|+|C|)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+1,MOD=1e9+7;
class ExSAM {
public:
struct node {
int len,link;
map <char,int> son;
node() { len=0,link=0; son.clear(); }
} st[MAXN<<1];
int siz; ExSAM() { siz=1; }
private:
inline int newch(int lst,char c) {
int cur=st[lst].son[c];
if(st[cur].len) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].link=st[q].link,st[r].len=st[p].len+1;
for(auto e:st[q].son) if(st[e.second].len) st[r].son.insert(e);
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
vector <int> G[MAXN<<1];
int ans[MAXN<<1],cnt[MAXN<<1][3];
inline void insert(int id,const string &str) {
int pos=1;
for(auto c:str) {
if(st[pos].son.find(c)==st[pos].son.end()) st[pos].son[c]=++siz;
pos=st[pos].son[c];
++cnt[pos][id];
}
}
inline void build() {
queue <pair<int,char> > Q;
for(auto e:st[1].son) Q.push(make_pair(1,e.first));
while(!Q.empty()) {
int lst=newch(Q.front().first,Q.front().second);
Q.pop();
for(auto e:st[lst].son) Q.push(make_pair(lst,e.first));
}
}
inline void solve() {
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
cnt[p][0]+=cnt[v][0];
cnt[p][1]+=cnt[v][1];
cnt[p][2]+=cnt[v][2];
}
int k=cnt[p][0]*cnt[p][1]%MOD*cnt[p][2]%MOD;
int L=st[st[p].link].len+1,R=st[p].len;
ans[L]=(ans[L]+k)%MOD,ans[R+1]=(ans[R+1]+MOD-k)%MOD;
};
dfs(dfs,1);
}
} SAM;
signed main() {
string A,B,C;
cin>>A>>B>>C;
SAM.insert(0,A),SAM.insert(1,B),SAM.insert(2,C);
SAM.build(),SAM.solve();
int L=min(A.length(),min(B.length(),C.length()));
for(int i=1;i<=L;++i) {
SAM.ans[i]=(SAM.ans[i]+SAM.ans[i-1])%MOD;
cout<<SAM.ans[i]<<" ";
}
cout<<"\n";
return 0;
}
13. [CF235C] - Cyclical Quest
先建出 \(\oper{SAM}(S)\)，考虑如何处理某个 \(T\) 的循环同构串，显然对于每个 \(T\) 复制两遍，用 \(T+T\) 在 SAM 上匹配，记录最长的匹配后缀长度 \(len\)，和 SAM 上的对应节点 \(p\)，当我们出现 \(len=|T|\) 的情况就统计答案，当匹配之后出现 \(len>|T|\) 的情况时，我们不断减少 \(len\)，并且在 SAM 上跳 \(\oper{link}(p)\) 直到 \(len=|T|\in[\oper{minlen}(p),\oper{maxlen(p)}]\)
对每个串分别匹配，注意到本质相同的循环同构串只算一种，因此我们可以用 kmp 处理出 \(T\) 的最小整周期 \(P\)，答案输出时除以 \(p\) 即可
时间复杂度 \(\Theta(|S|+\sum|T|)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+1;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0; son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
int cnt[MAXN<<1];
vector <int> G[MAXN<<1];
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
++cnt[cur];
lst=cur;
}
inline void dfs(int p) {
for(int v:G[p]) dfs(v),cnt[p]+=cnt[v];
}
inline int root(string s) {
int n=s.length();
vector <int> kmp(n+1,0);
s="#"+s;
for(int i=2,j=0;i<=n;++i) {
while(j&&s[j+1]!=s[i]) j=kmp[j];
if(s[j+1]==s[i]) ++j;
kmp[i]=j;
}
int rt=n-kmp[n];
if(n%rt==0) return n/rt;
return 1;
}
signed main() {
string s;
cin>>s;
for(auto ch:s) insert(ch);
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
dfs(1);
int q;
cin>>q;
while(q--) {
int ans=0,len=0,p=1;
string t;
cin>>t;
auto match=[&](char c) -> void {
if(st[p].son.find(c)!=st[p].son.end()) ++len,p=st[p].son[c];
else {
while(p&&st[p].son.find(c)==st[p].son.end()) p=st[p].link;
if(!p) len=0,p=1;
else len=st[p].len+1,p=st[p].son[c];
}
};
auto resize=[&]() -> void {
while(len>(int)t.length()) {
--len;
if(len<=st[st[p].link].len) p=st[p].link;
}
};
for(auto ch:t) match(ch),resize();
for(auto ch:t) {
if(len==(int)t.length()) ans+=cnt[p];
match(ch),resize();
}
cout<<ans/root(t)<<"\n";
}
return 0;
}
14. [P5212] - SubString
显然询问直接暴力找 \(\oper{pos}(T)\) 然后输出 \(\oper{cnt}(\oper{pos}(T))\) 即可，因此问题转化为动态维护 \(\oper{cnt}(p)\)
考虑统计 \(\oper{cnt}(p)\) 时，我们曾经得到过结论：\(\oper{cnt}(p)\) 等于 Parent Tree 上 \(p\) 的子树中 \(\oper{suffix}(r)\) 的数量，因此当我们插入一个新字符 \(S_{n+1}\) 后，其对 \(\oper{cnt}(p)\) 的贡献等价于执行 \(\oper{suffix}(n+1)\to \oper{root}\) 的路径加，而由于在建立 SAM 的时候我们会不断改变 Parent Tree 的形态，因此引入另一个技巧：
Trick #2：
Link Cut Tree 维护 Parent Tree 信息
注意到维护 Parent Tree 只有连边、断边、路径加、单点查四种操作，因此直接用 LCT 维护信息即可
时间复杂度 \(\Theta(|S|\log|S|+|T|)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e6+1;
class LinkCutTree {
public:
int ch[MAXN][2],fa[MAXN];
int val[MAXN],sum[MAXN],siz[MAXN];
int rev[MAXN],add[MAXN];
inline void clear(int p) {
ch[p][0]=ch[p][1]=fa[p]=0;
val[p]=sum[p]=siz[p]=0;
rev[p]=add[p]=0;
}
inline void pushup(int p) {
clear(0);
sum[p]=val[p]+sum[ch[p][0]]+sum[ch[p][1]];
siz[p]=1+siz[ch[p][0]]+siz[ch[p][1]];
}
inline void revtag(int p) {
if(p) rev[p]^=1,swap(ch[p][0],ch[p][1]);
}
inline void addtag(int p,int k) {
if(p) add[p]+=k,sum[p]+=siz[p]*k,val[p]+=k;
}
inline void pushdown(int p) {
if(add[p]) addtag(ch[p][0],add[p]),addtag(ch[p][1],add[p]),add[p]=0;
if(rev[p]) revtag(ch[p][0]),revtag(ch[p][1]),rev[p]=0;
}
inline bool isroot(int p) {
return p!=ch[fa[p]][0]&&p!=ch[fa[p]][1];
}
inline int son(int p) {
return p==ch[fa[p]][1];
}
inline void rotate(int p) {
int u=fa[p],v=fa[u],k=son(p);
if(!isroot(u)) ch[v][son(u)]=p;
ch[u][k]=ch[p][k^1],fa[ch[p][k^1]]=u;
ch[p][k^1]=u,fa[u]=p,fa[p]=v;
pushup(u),pushup(p);
}
inline void update(int p) {
if(!isroot(p)) update(fa[p]);
pushdown(p);
}
inline void splay(int p) {
update(p);
while(!isroot(p)) {
if(!isroot(fa[p])) rotate(son(p)==son(fa[p])?fa[p]:p);
rotate(p);
}
}
inline int access(int p) {
int u=0;
while(p) {
splay(p),ch[p][1]=u,pushup(p);
u=p,p=fa[p];
}
return u;
}
inline void makeroot(int p) {
revtag(access(p));
}
inline int findroot(int p) {
access(p),splay(p),pushdown(p);
while(ch[p][0]) p=ch[p][0],pushdown(p);
splay(p);
return p;
}
inline void link(int u,int v) {
makeroot(u),splay(u),fa[u]=v;
}
inline void cut(int u,int v) {
makeroot(u),access(v),splay(v);
fa[u]=ch[v][0]=0,pushup(v);
}
inline int split(int u,int v) {
makeroot(u);
return access(v);
}
} LCT;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
inline void insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1,LCT.link(1,cur);
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q,LCT.link(cur,q);
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
LCT.val[r]=LCT.sum[LCT.split(q,q)],LCT.pushup(r);
LCT.link(r,st[q].link),LCT.cut(q,st[q].link);
st[cur].link=st[q].link=r;
LCT.link(cur,r),LCT.link(q,r);
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur,LCT.addtag(LCT.split(1,cur),1);
}
inline void decode(string &str,int mask) {
int n=(int)str.length();
for(int i=0;i<n;++i) {
mask=(mask*131+i)%n;
swap(str[i],str[mask]);
}
}
inline int match(const string &str) {
int p=1;
for(auto c:str) {
if(st[p].son.find(c)==st[p].son.end()) return 0;
p=st[p].son[c];
}
return p;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int mask=0,q;
string str;
cin>>q>>str;
for(auto c:str) insert(c);
while(q--) {
string oper,str;
cin>>oper>>str;
decode(str,mask);
if(oper=="ADD") {
for(auto c:str) insert(c);
}
if(oper=="QUERY") {
int ans=0,u=match(str);
if(u!=0) ans=LCT.sum[LCT.split(u,u)];
mask^=ans;
cout<<ans<<"\n";
}
}
return 0;
}
15. [CF653F] - Paper task
看到本质不同子串先考虑用 SAM 去重，对于 SAM 上的每个节点 \(p\)，我们维护 \(\oper{endpos}(p)\) 中的任意一个，那么问题就转化成：对于右端点在 \(R\)，左端点在 \([l,r]\) 之间的所有括号串判断是否合法
对于这个问题，我们可以将括号序列看成 \(+1,-1\) 序列，左括号为正，右括号为负，那么判定 \(S[L\dots R]\) 是否合法等价于如下两个条件：
- \(S[L\dots R]\) 的所有后缀和 \(\le 0\)
- \(S[L\dots R]\) 的总和 \(=0\)
先考虑第一个限制，容易发现满足第一个性质合法的 \(L\) 一定是 \([l,r]\) 的一段后缀，具有可二分性，检验的时候用 ST 表维护前缀和的一段 rmq 即可
假设我们求出了满足第一个条件的所有左端点 \([l',r]\)，我们只需要在 \([l'-1,r-1]\) 求出有多少 \(sum_i=sum_r\)，显然可以对 \(sum\) 开桶，查询时在里面二分即可
时间复杂度 \(\Theta(n\log n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e5+1;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1,endpos[MAXN<<1];
inline void insert(int i,char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur,endpos[cur]=i;
}
vector <int> G[MAXN<<1],buc[MAXN<<1];
char str[MAXN];
int sum[MAXN],f[MAXN][21];
inline int bit(int x) { return 1<<x; }
inline int qmin(int l,int r) {
int k=__lg(r-l+1);
return min(f[l][k],f[r-bit(k)+1][k]);
}
signed main() {
int n;
scanf("%lld%s",&n,str+1);
for(int i=1;i<=n;++i) {
insert(i,str[i]);
sum[i]=(str[i]=='(')?(sum[i-1]+1):(sum[i-1]-1);
f[i][0]=sum[i];
}
sum[0]=f[0][0]=0;
for(int i=0;i<=n;++i) buc[sum[i]+n].push_back(i);
for(int k=1;k<=20;++k) {
for(int i=0;i+bit(k-1)<=n;++i) {
f[i][k]=min(f[i][k-1],f[i+bit(k-1)][k-1]);
}
}
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
if(endpos[v]) endpos[p]=endpos[v];
}
};
dfs(dfs,1);
int ans=0;
for(int i=2;i<=siz;++i) {
auto solve=[&](int ul,int ur,int R) -> int {
int l=ul,r=ur,res=ur+1;
while(l<=r) {
int mid=(l+r)>>1;
auto check=[&](int k) -> bool {
return qmin(k-1,R-1)>=sum[R];
};
if(check(mid)) res=mid,r=mid-1;
else l=mid+1;
}
if(res>ur) return 0;
return upper_bound(buc[sum[R]+n].begin(),buc[sum[R]+n].end(),ur-1)-
lower_bound(buc[sum[R]+n].begin(),buc[sum[R]+n].end(),res-1);
};
int tmp=solve(endpos[i]-st[i].len+1,endpos[i]-(st[st[i].link].len+1)+1,endpos[i]);
ans+=tmp;
}
printf("%lld\n",ans);
return 0;
}
16. [P4022] - 熟悉的文章
显然可以先二分 \(L_0\) 的值，我们可以写出一个显然的 dp：设 \(dp_i\) 表示 \(S[1\dots i]\) 的最大匹配长度，那么我们有如下的转移：
\[dp_i=\max_j\{dp_j+(i-j)\mid S[j+1\dots i]\subseteq T\text{ and } j\le i-L\}
\]
\]
当然 \(dp_i\) 也可以直接从 \(dp_{i-1}\) 处转移
其中 \(S[j+1\dots i]\subseteq T\) 表示 \(S[j+1\dots i]\) 至少是 \(T\) 中某一个串的子串，容易发现这样的 \(j\) 构成一个以 \(i\) 为左端点的连续段，而其右端点可以通过求出最长匹配段 \(match_i\) 得到，而 \(match_i\) 可以直接用 \(S[1\dots i]\) 在 \(\oper{SAM}(T_1,T_2\dots,T_m)\) 上匹配后缀求，因此状态转移可以写成：
\[dp_i=\max_j\{dp_j+(i-j)\mid i-match_i\le j\le i-L\}
\]
\]
注意到 \(i-match_i\) 单调不降，因此我们可以直接用单调队列优化转移
时间复杂度 \(\Theta(\sum|T|+n\log n)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1.1e6+1;
class ExSAM {
public:
struct node {
int len,link;
map <char,int> son;
node() { len=0,link=0; son.clear(); }
} st[MAXN<<1];
int siz; ExSAM() { siz=1; }
private:
inline int newch(int lst,char c) {
int cur=st[lst].son[c];
if(st[cur].len) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].link=st[q].link,st[r].len=st[p].len+1;
for(auto e:st[q].son) if(st[e.second].len) st[r].son.insert(e);
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
inline void insert(const string &str) {
int pos=1;
for(auto c:str) {
if(st[pos].son.find(c)==st[pos].son.end()) st[pos].son[c]=++siz;
pos=st[pos].son[c];
}
}
inline void build() {
queue <pair<int,char> > Q;
for(auto e:st[1].son) Q.push(make_pair(1,e.first));
while(!Q.empty()) {
int lst=newch(Q.front().first,Q.front().second);
Q.pop();
for(auto e:st[lst].son) Q.push(make_pair(lst,e.first));
}
}
} SAM;
int len[MAXN],q[MAXN],dp[MAXN];
inline void solve() {
string str;
cin>>str;
int n=str.length();
str="#"+str;
for(int i=1,p=1,l=0;i<=n;++i) {
auto match=[&](char c) -> void {
if(SAM.st[p].son.find(c)!=SAM.st[p].son.end()) {
++l,p=SAM.st[p].son[c];
} else {
while(p&&SAM.st[p].son.find(c)==SAM.st[p].son.end()) p=SAM.st[p].link;
if(!p) p=1,l=0;
else l=SAM.st[p].len+1,p=SAM.st[p].son[c];
}
};
match(str[i]),len[i]=l;
}
int l=0,r=n,res=0;
while(l<=r) {
int mid=(l+r)>>1;
auto check=[&](int k) -> bool {
int head=0,tail=1;
for(int i=0;i<k;++i) dp[i]=0;
for(int i=k;i<=n;++i) {
if(i>k) {
while(head<=tail&&dp[q[tail]]-q[tail]<dp[i-k]-(i-k)) --tail;
q[++tail]=i-k;
}
while(head<=tail&&q[head]<i-len[i]) ++head;
if(head>tail) dp[i]=dp[i-1];
else dp[i]=max(dp[q[head]]+(i-q[head]),dp[i-1]);
}
return dp[n]*10>=n*9;
};
if(check(mid)) l=mid+1,res=mid;
else r=mid-1;
}
cout<<res<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int q,m;
cin>>q>>m;
for(int i=1;i<=m;++i) {
string str;
cin>>str;
SAM.insert(str);
}
SAM.build();
while(q--) solve();
return 0;
}
17. [CF204E] - Little Elephant and Strings
同样的，在广义 SAM 上用线段树合并维护每个节点对应的字符串在哪些模式串中出现过，以及分别的出现次数
然后我们可以统计出哪些位置 \(p\) 对答案有贡献，由于答案统计的是所有子串而非本质不同子串，而这些 \(p\) 对答案的贡献应该恰好是 \((\oper{maxlen}(p)-\oper{minlen}(p)+1)\times\oper{cnt}(p)\)，我们可以把答案数组也建立一棵线段树，统计贡献的时候就把 \(p\) 对应的线段树扩倍然后加到答案的线段树上，这个操作只要在合并的时候多传一个参数就可以解决
时间复杂度 \(\Theta(A\log A)\)，其中 \(A=\sum|a_i|\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+1;
int n,k;
class SegmentTree {
private:
struct node {
int cnt,ls,rs;
ll sum;
node() { sum=0,cnt=0,ls=rs=0; }
} tree[MAXN*24];
inline void pushup(int pos) {
tree[pos].cnt=tree[tree[pos].ls].cnt+tree[tree[pos].rs].cnt;
tree[pos].sum=tree[tree[pos].ls].sum+tree[tree[pos].rs].sum;
}
int siz;
public:
SegmentTree() { siz=0; }
inline void Build(int l,int r,int &pos) {
if(!pos) pos=++siz;
if(l==r) return ;
int mid=(l+r)>>1;
Build(l,mid,tree[pos].ls);
Build(mid+1,r,tree[pos].rs);
}
inline void Insert(int u,int l,int r,int &pos) {
if(!pos) pos=++siz;
if(l==r) {
tree[pos].cnt|=1;
++tree[pos].sum;
return ;
}
int mid=(l+r)>>1;
if(u<=mid) Insert(u,l,mid,tree[pos].ls);
else Insert(u,mid+1,r,tree[pos].rs);
pushup(pos);
}
inline void Merge(ll k,int l,int r,int &des,int src) {
if(!des||!src) { des|=src; return ; }
if(l==r) {
tree[des].sum+=k*tree[src].sum;
tree[des].cnt|=tree[src].cnt;
return ;
}
int mid=(l+r)>>1;
Merge(k,l,mid,tree[des].ls,tree[src].ls);
Merge(k,mid+1,r,tree[des].rs,tree[src].rs);
pushup(des);
}
inline int Count(int pos) { return tree[pos].cnt; }
inline ll Query(int u,int l,int r,int pos) {
if(l==r) return tree[pos].sum;
int mid=(l+r)>>1;
if(u<=mid) return Query(u,l,mid,tree[pos].ls);
else return Query(u,mid+1,r,tree[pos].rs);
}
} T;
int root[MAXN<<1];
vector <int> G[MAXN<<1];
class ExSAM {
public:
struct node {
int len,link;
map <char,int> son;
node() { len=0,link=0; son.clear(); }
} st[MAXN<<1];
int siz; ExSAM() { siz=1; }
private:
inline int newch(int lst,char c) {
int cur=st[lst].son[c];
if(st[cur].len) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].link=st[q].link,st[r].len=st[p].len+1;
for(auto e:st[q].son) if(st[e.second].len) st[r].son.insert(e);
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
inline void insert(int id,const string &str) {
int pos=1;
for(auto c:str) {
if(st[pos].son.find(c)==st[pos].son.end()) st[pos].son[c]=++siz;
pos=st[pos].son[c];
T.Insert(id,1,n,root[pos]);
}
}
inline void build() {
queue <pair<int,char> > Q;
for(auto e:st[1].son) Q.push(make_pair(1,e.first));
while(!Q.empty()) {
int lst=newch(Q.front().first,Q.front().second);
Q.pop();
for(auto e:st[lst].son) Q.push(make_pair(lst,e.first));
}
}
inline void solve() {
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
T.Merge(1,1,n,root[p],root[v]);
}
if(p>1&&T.Count(root[p])>=k) T.Merge(st[p].len-st[st[p].link].len,1,n,root[0],root[p]);
};
dfs(dfs,1);
}
} SAM;
string str[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;++i) {
cin>>str[i];
SAM.insert(i,str[i]);
}
T.Build(1,n,root[0]);
SAM.build();
SAM.solve();
for(int i=1;i<=n;++i) cout<<T.Query(i,1,n,root[0])<<" "; cout<<"\n";
return 0;
}
18. [P4081] - Standing Out from the Herd P
首先建出广义 SAM，在 Parent Tree 上维护每个节点代表的串在哪个模式串里出现过，如果有多个则这个节点不合法，否则对对应的模式串产生 \(\oper{maxlen}(p)-\oper{minlen}(p)+1\) 的贡献，直接维护即可
时间复杂度 \(\Theta(\sum |S_i|)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
int n,ans[MAXN],endpos[MAXN<<1];
vector <int> G[MAXN<<1];
class ExSAM {
public:
struct node {
int len,link;
map <char,int> son;
node() { len=0,link=0; son.clear(); }
} st[MAXN<<1];
int siz; ExSAM() { siz=1; }
private:
inline int newch(int lst,char c) {
int cur=st[lst].son[c];
if(st[cur].len) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].link=st[q].link,st[r].len=st[p].len+1;
for(auto e:st[q].son) if(st[e.second].len) st[r].son.insert(e);
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
inline void insert(int id,const string &str) {
int pos=1;
for(auto c:str) {
if(st[pos].son.find(c)==st[pos].son.end()) st[pos].son[c]=++siz;
pos=st[pos].son[c];
if(!endpos[pos]) endpos[pos]=id;
else endpos[pos]=-1;
}
}
inline void build() {
queue <pair<int,char> > Q;
for(auto e:st[1].son) Q.push(make_pair(1,e.first));
while(!Q.empty()) {
int lst=newch(Q.front().first,Q.front().second);
Q.pop();
for(auto e:st[lst].son) Q.push(make_pair(lst,e.first));
}
}
inline void solve() {
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
if(endpos[p]==-1||endpos[v]==-1) endpos[p]=-1;
else if(endpos[p]==0||endpos[v]==0) endpos[p]|=endpos[v];
else if(endpos[p]!=endpos[v]) endpos[p]=-1;
}
if(endpos[p]>0) ans[endpos[p]]+=st[p].len-st[st[p].link].len;
};
dfs(dfs,1);
}
} SAM;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;++i) {
string str;
cin>>str;
SAM.insert(i,str);
}
SAM.build(),SAM.solve();
for(int i=1;i<=n;++i) cout<<ans[i]<<"\n";
return 0;
}
19. [CF1037H] - Security
考虑直接在 \(\oper{SAM}(S)\) 上贪心地去匹配一个字典序大于 \(T\) 的字符串，问题转化为判断某个节点 \(p\) 对应的长度为 \(len\) 的字符串是否在 \(S[l\dots r]\) 中出现过，这里引入一个常见 Trick：
Trick #3：
查询 \(S\) 的某个子串 \(S'\) 是否是 \(S[l\dots r]\) 的子串的问题，可以等价于 \(\oper{endpos}(\oper{pos}(S'))\) 中是否有 \([l+|S'|-1,r]\) 这一段区间内的元素
考虑从这些字符串的结尾位置入手，问题等价于查询 \(\oper{endpos}(p)\) 中有没有 \(\oper{endpos}\) 位于 \([l+len-1,r]\) 这一段区间内，考虑用线段树合并维护 \(\oper{endpos}\) 集合，直接在对应的线段树上区间查询即可
时间复杂度 \(\Theta((|S|+\sum|T|)\log |S|)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
class SegmentTree {
private:
int siz;
struct node {
int cnt,ls,rs;
node() { cnt=0,ls=rs=0; }
} tree[MAXN*50];
inline void pushup(int pos) {
tree[pos].cnt=tree[tree[pos].ls].cnt+tree[tree[pos].rs].cnt;
}
public:
SegmentTree() { siz=0; }
inline void Insert(int u,int l,int r,int &pos) {
if(!pos) pos=++siz;
if(l==r) { tree[pos].cnt|=1; return ; }
int mid=(l+r)>>1;
if(u<=mid) Insert(u,l,mid,tree[pos].ls);
if(mid<u) Insert(u,mid+1,r,tree[pos].rs);
pushup(pos);
}
inline int Merge(int l,int r,int des,int src) {
if(!des||!src) { return des|src; }
if(l==r) { tree[des].cnt|=tree[src].cnt; return des; }
int mid=(l+r)>>1,id=++siz;
tree[id].ls=Merge(l,mid,tree[des].ls,tree[src].ls);
tree[id].rs=Merge(mid+1,r,tree[des].rs,tree[src].rs);
pushup(id);
return id;
}
inline bool Query(int ul,int ur,int l,int r,int pos) {
if(ul>ur||!pos) return false;
if(ul<=l&&r<=ur) return tree[pos].cnt>0;
int mid=(l+r)>>1; bool ret=false;
if(ul<=mid) ret|=Query(ul,ur,l,mid,tree[pos].ls);
if(mid<ur) ret|=Query(ul,ur,mid+1,r,tree[pos].rs);
return ret;
}
} T;
int n,root[MAXN<<1];
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
inline void insert(int endpos,char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur;
T.Insert(endpos,1,n,root[cur]);
}
vector <int> G[MAXN<<1];
inline void solve() {
int l,r;
string T;
cin>>l>>r>>T;
int m=T.length();
string ans="";
auto dfs=[&](auto self,int d,int p) -> bool {
if(d>=r-l+1) return false;
if(d>m) return true;
char fir=(d<m)?T[d]:'a';
for(char c=fir;c<='z';++c) {
if(st[p].son.find(c)==st[p].son.end()) continue;
int u=st[p].son[c];
if(::T.Query(l+d,r,1,n,root[u])) {
if(d<m&&c==fir&&!self(self,d+1,u)) continue;
ans=c+ans;
return true;
}
}
return false;
};
bool ret=dfs(dfs,0,1);
if(!ret) cout<<"-1\n";
else cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
string S;
cin>>S; n=S.length();
for(int i=0;i<n;++i) insert(i+1,S[i]);
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
root[p]=T.Merge(1,n,root[p],root[v]);
}
};
dfs(dfs,1);
int q;
cin>>q;
while(q--) solve();
return 0;
}
20. [P4094] - 字符串
显然答案具有可二分性，考虑二分答案，问题转化为判定某个 \(S[c\dots k]\) 是否在 \(S[a\dots b]\) 中出现过，类似上一题的做法，用线段树合并维护 \(\oper{endpos}\) 集合找到 \(\oper{pos}(S[c\dots k])\)，然后再去找对应的 \(\oper{endpos}\) 集合中是否有属于 \([a+len-1,b]\) 中的元素
问题转化为如何快速找 \(\oper{pos}(S[c\dots k])\)，这里引入一个常用技巧：
Trick #4：
为了求出 \(\oper{pos}(S[l\dots r])\)，我们先记录下所有的 \(\oper{suffix}(r)\)，那么 \(\oper{pos}(S[l\dots r])\) 一定在 Parent Tree 中 \(\oper{suffix}(r)\) 到 \(\oper{root}\) 的路径上，因此可以用树上倍增求出 \(\oper{len}(p)\ge r-l+1\) 的最后一个节点，此时 \(p\) 即为 \(\oper{pos}(S[l\dots r])\)
因此这个问题我们直接在树上倍增求出 \(p=\oper{pos}(S[c\dots k])\)，然后在 \(\oper{endpos}(p)\) 中做区间查即可
时间复杂度 \(\Theta(n\log n+m\log^2n)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int n,q;
class SegmentTree {
private:
int siz;
struct node {
int cnt,ls,rs;
node() { cnt=0,ls=rs=0; }
} tree[MAXN*50];
inline void pushup(int pos) {
tree[pos].cnt=tree[tree[pos].ls].cnt+tree[tree[pos].rs].cnt;
}
public:
SegmentTree() { siz=0; }
inline void Insert(int u,int l,int r,int &pos) {
if(!pos) pos=++siz;
if(l==r) { tree[pos].cnt|=1; return ; }
int mid=(l+r)>>1;
if(u<=mid) Insert(u,l,mid,tree[pos].ls);
if(mid<u) Insert(u,mid+1,r,tree[pos].rs);
pushup(pos);
}
inline int Merge(int l,int r,int des,int src) {
if(!des||!src) { return des|src; }
if(l==r) { tree[des].cnt|=tree[src].cnt; return des; }
int mid=(l+r)>>1,id=++siz;
tree[id].ls=Merge(l,mid,tree[des].ls,tree[src].ls);
tree[id].rs=Merge(mid+1,r,tree[des].rs,tree[src].rs);
pushup(id);
return id;
}
inline bool Query(int ul,int ur,int l,int r,int pos) {
if(ul>ur||!pos) return false;
if(ul<=l&&r<=ur) return tree[pos].cnt>0;
int mid=(l+r)>>1; bool ret=false;
if(ul<=mid) ret|=Query(ul,ur,l,mid,tree[pos].ls);
if(mid<ur) ret|=Query(ul,ur,mid+1,r,tree[pos].rs);
return ret;
}
} T;
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
int root[MAXN<<1],endpos[MAXN];
inline void insert(int pos,char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
lst=cur;
T.Insert(pos,1,n,root[cur]);
endpos[pos]=cur;
}
vector <int> G[MAXN<<1];
int fa[MAXN<<1][20];
char s[MAXN];
inline void solve() {
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
int l=c,r=d,res=c-1;
while(l<=r) {
int mid=(l+r)>>1;
auto check=[&](int k) -> bool {
int len=k-c+1,u=endpos[k];
for(int x=19;x>=0;--x) {
if(st[fa[u][x]].len>=len) u=fa[u][x];
}
return T.Query(a+len-1,b,1,n,root[u]);
};
if(check(mid)) res=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",res-c+1);
}
signed main() {
scanf("%d%d%s",&n,&q,s+1);
for(int i=1;i<=n;++i) insert(i,s[i]);
for(int i=2;i<=siz;++i) fa[i][0]=st[i].link,G[st[i].link].push_back(i);
for(int k=1;k<20;++k) {
for(int i=1;i<=siz;++i) {
fa[i][k]=fa[fa[i][k-1]][k-1];
}
}
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
root[p]=T.Merge(1,n,root[p],root[v]);
}
};
dfs(dfs,1);
while(q--) solve();
return 0;
}
21. [SP687] - Repeats
考虑所有循环次数 \(\ge 1\) 的串，枚举循环节长度 \(len\)，假如我们把所有 \(len\) 倍数的节点设为关键点，那么可以发现这样的串一定至少经过两个关键点，那么我们可以枚举任意两个相邻的关键点 \(len_k,len_{k+1}\)，然后我们求出 \(\oper{lcp}(len_k,len_{k+1})\)，\(\oper{lcs}(len_k,len_{k+1})\)，此时我们得到两个相同的，长度为 \(\oper{lcp}+\oper{lcs}-1\)，且间隔为 \(len\) 的两个串，容易发现我们此时能得到一个长度为 \(\oper{lcp}+\oper{lcs}+len-1\)，且有周期 \(len\) 的字符串，因此可以用 \(\left\lfloor\dfrac{\oper{lcp}+\oper{lcs}-1}{len}\right\rfloor+1\) 去更新答案
因此原问题转成了快速求任意前缀 \(\oper{lcs}\) 和任意后缀 \(\oper{lcp}\)，可以用后缀数组转成 \(height_i\) 上的 rmq 问题用 ST 表加速即可，也可以用 Parent Tree 上 LCA 来加速
另：本题有直接用 SAM + 线段树维护的本质做法
时间复杂度 \(\Theta(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=50001;
struct FastLCP {
int sa[MAXN],rnk[MAXN],len[MAXN],wt[MAXN],ht[MAXN];
inline void BuildSA(char str[],int n) {
for(int i=1;i<=n;++i) sa[i]=i;
sort(sa+1,sa+n+1,[&](int x,int y){ return str[x]<str[y]; });
for(int i=1;i<=n;) {
int j=i;
while(j<n&&str[sa[j+1]]==str[sa[i]]) ++j;
len[i]=j-i+1;
while(i<=j) rnk[sa[i++]]=j;
}
for(int k=1;k<n;k=k<<1) {
for(int l=1;l<=n;++l) {
if(len[l]>1) {
int r=l+len[l]-1;
for(int i=l;i<=r;++i) wt[sa[i]]=(sa[i]+k>n)?0:rnk[sa[i]+k];
sort(sa+l,sa+r+1,[&](int x,int y){ return wt[x]<wt[y]; });
for(int i=l;i<=r;) {
int j=i;
while(j<r&&wt[sa[j+1]]==wt[sa[i]]) ++j;
len[i]=j-i+1;
while(i<=j) rnk[sa[i++]]=j;
}
l=r;
}
}
}
for(int i=1,k=0;i<=n;++i) {
if(k>0) --k;
while(str[i+k]==str[sa[rnk[i]-1]+k]) ++k;
ht[rnk[i]]=k;
}
}
int f[MAXN][20];
inline int bit(int x) { return 1<<x; }
inline void init(int n) {
for(int i=1;i<=n;++i) f[i][0]=ht[i];
for(int k=1;k<20;++k) {
for(int i=1;i+bit(k-1)<=n;++i) {
f[i][k]=min(f[i][k-1],f[i+bit(k-1)][k-1]);
}
}
}
inline int qmin(int l,int r) {
int k=__lg(r-l+1);
return min(f[l][k],f[r-bit(k)+1][k]);
}
inline int lcp(int x,int y) {
if(rnk[x]>rnk[y]) swap(x,y);
return qmin(rnk[x]+1,rnk[y]);
}
} LCP,LCS;
char str[MAXN];
inline void solve() {
int n,ans=1;
cin>>n;
for(int i=1;i<=n;++i) cin>>str[i];
LCP.BuildSA(str,n),LCP.init(n);
reverse(str+1,str+n+1);
LCS.BuildSA(str,n),LCS.init(n);
for(int len=1;len<=n;++len) {
for(int i=1;i+len<=n;i+=len) {
int x=LCP.lcp(i,i+len),y=LCS.lcp(n-i+1,n-(i+len)+1);
int tot=x+y;
if(x&&y) --tot;
ans=max(ans,tot/len+1);
}
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T; cin>>T;
while(T--) solve();
return 0;
}
22. [P6292] - 区间本质不同子串个数
本问题实际上相似于区间数颜色问题，考虑扫描线，对于每个 SAM 上的节点 \(p\)，我们维护出其最大的 \(\oper{endpos}\)，然后求出以这个位置 \(r\) 为右端点时，对于 \(r-\oper{maxlen}(p)+1\sim r-\oper{minlen}(p)+1\) 中的每个 \(l\)，\(S[l\dots r]\) 都是新的本质不同的子串，因此我们可以在这些位置上打上 \(+1\) 标记，查询时等价于查询 \([l,r]\) 一段的后缀和，显然这些贡献可以直接用线段树维护
每当我们新插入一个字符 \(S_{r+1}\) 时，我们会把 Parent Tree 上所有 \(\oper{suffix}(r+1)\to \oper{root}\) 路径上的节点对应的 \(\oper{endpos}\) 修改成 \(r+1\)，因此我们只需要在 Parent Tree 上进行路径修改，并且在修改的时候顺便更新线段树上的标记
接下来解决树上修改，注意到这个操作很像 LCT 的 access 操作，当我们在 Parent Tree 上用 LCT 维护后，每次我们修改的时候，只需要跳若干个连续的实链统计贡献节课
这是因为一段连续的实链在 Parent Tree 上一定代表的是若干左端点连续、右端点相同的后缀，因此每个实链的贡献可以整体考虑，假设当前实链的最低点为 \(p\)，其实链根的父亲为 \(f\)，那么这一段实链的长度区间即为 \((\oper{len}(f),\oper{len}(p)]\)，找到原有的右端点，把对应段的贡献 \(-1\)，并且找到新的右端点把对应段的贡献 \(+1\)，access 到根之后在 Splay 上打一个覆盖右端点的懒标记即可，注意 \(f\) 要在 LCT 上把 \(p\) Splay 到根后求出 \(fa_p\)，而非直接求 \(\oper{link}(p)\)
注意由于我们可以离线，因此可以预处理出整棵树的 Parent Tree 再用 LCT 维护，避免了修改树形态的问题
时间复杂度 \(\Theta(n\log^2 n+q\log n)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
int n,q;
class SuffixAutomaton {
public:
struct node {
int link,len;
map <char,int> son;
node() { link=0,len=0,son.clear(); }
} st[MAXN<<1];
int siz=1,lst=1;
inline int insert(char c) {
int cur=++siz;
st[cur].len=st[lst].len+1;
int p=lst;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r]=st[q],st[r].len=st[p].len+1;
st[cur].link=st[q].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return lst=cur;
}
} SAM;
class SegmentTree {
private:
struct node {
int sum,tag;
} tree[MAXN<<2];
inline int left(int x) { return x<<1; }
inline int right(int x) { return x<<1|1; }
inline void pushup(int pos) { tree[pos].sum=tree[left(pos)].sum+tree[right(pos)].sum; }
inline void addtag(int k,int l,int r,int pos) {
tree[pos].tag+=k,tree[pos].sum+=k*(r-l+1);
}
inline void pushdown(int l,int r,int pos) {
int mid=(l+r)>>1;
addtag(tree[pos].tag,l,mid,left(pos));
addtag(tree[pos].tag,mid+1,r,right(pos));
tree[pos].tag=0;
}
public:
inline void Modify(int ul,int ur,int k,int l=1,int r=n,int pos=1) {
if(ul<=l&&r<=ur) { addtag(k,l,r,pos); return ; }
pushdown(l,r,pos);
int mid=(l+r)>>1;
if(ul<=mid) Modify(ul,ur,k,l,mid,left(pos));
if(mid<ur) Modify(ul,ur,k,mid+1,r,right(pos));
pushup(pos);
}
inline int Query(int ul,int ur,int l=1,int r=n,int pos=1) {
if(ul<=l&&r<=ur) return tree[pos].sum;
pushdown(l,r,pos);
int mid=(l+r)>>1,ret=0;
if(ul<=mid) ret+=Query(ul,ur,l,mid,left(pos));
if(mid<ur) ret+=Query(ul,ur,mid+1,r,right(pos));;
return ret;
}
} TR;
class LinkCutTree {
public:
int ch[MAXN<<1][2],fa[MAXN<<1];
int cov[MAXN<<1],endpos[MAXN<<1];
inline void covtag(int p,int k) {
if(p) cov[p]=endpos[p]=k;
}
inline void pushdown(int p) {
if(!cov[p]) return ;
covtag(ch[p][0],cov[p]),covtag(ch[p][1],cov[p]);
cov[p]=0;
}
inline bool isroot(int p) {
return ch[fa[p]][0]!=p&&ch[fa[p]][1]!=p;
}
inline int son(int p) {
return ch[fa[p]][1]==p;
}
inline void update(int p) {
if(!isroot(p)) update(fa[p]);
pushdown(p);
}
inline void rotate(int p) {
int u=fa[p],v=fa[u],k=son(p);
if(!isroot(u)) ch[v][son(u)]=p;
ch[u][k]=ch[p][k^1],fa[ch[p][k^1]]=u;
ch[p][k^1]=u,fa[u]=p,fa[p]=v;
}
inline void splay(int p) {
update(p);
while(!isroot(p)) {
if(!isroot(fa[p])) rotate(son(p)==son(fa[p])?fa[p]:p);
rotate(p);
}
}
inline void access(int p,int pos) {
int u=0;
while(p) {
splay(p),ch[p][1]=u;
int minlen=SAM.st[fa[p]].len+1,maxlen=SAM.st[p].len;
if(minlen<=maxlen) {
if(endpos[p]) {
TR.Modify(endpos[p]-maxlen+1,endpos[p]-minlen+1,-1);
}
TR.Modify(pos-maxlen+1,pos-minlen+1,1);
}
u=p,p=fa[p];
}
covtag(u,pos);
}
} LCT;
char str[MAXN];
vector <pair<int,int> > qry[MAXN];
int ans[MAXN<<1],endpos[MAXN];
signed main() {
scanf("%s%lld",str+1,&q);
n=strlen(str+1);
for(int i=1;i<=q;++i) {
int l,r;
scanf("%lld%lld",&l,&r);
qry[r].push_back(make_pair(l,i));
}
for(int i=1;i<=n;++i) {
endpos[i]=SAM.insert(str[i]);
}
for(int i=1;i<=SAM.siz;++i) LCT.fa[i]=SAM.st[i].link;
for(int i=1;i<=n;++i) {
LCT.access(endpos[i],i);
for(auto Q:qry[i]) {
ans[Q.second]=TR.Query(Q.first,i);
}
}
for(int i=1;i<=q;++i) printf("%lld\n",ans[i]);
return 0;
}
23. [CF666E] - Forensic Examination
首先考虑建立 \(\oper{SAM}(T_1,T_2,\dots,T_m)\)，然后在广义 SAM 上用线段树合并维护对于每个节点 \(p\)，\(p\) 对应的字符串在 \(T_l\sim T_r\) 中哪个文本串中出现次数最多，询问只要找到 \(\oper{pos}(S[pl\dots pr])\) 然后在对应的线段树做区间查询即可，问题只剩下如何找到 \(\oper{pos}(S[pl\dots pr])\)，显然的想法是直接倍增，但这里不一定能保证 \(\oper{pos}(S[1\dots pr])\) 一定存在，因此我们可以先考虑把 \(S\) 也加入广义 SAM 中，然后就能一样地在 Parent Tree 上倍增处理了
时间复杂度 \(\Theta(L\log m+q\log L)\)，其中 \(L=|S|+\sum|T_i|\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e5+1,INF=1e9;
struct Data {
int cnt,id;
Data(int _cnt=0,int _id=INF) { cnt=0,id=INF; }
inline friend Data operator +(const Data &A,const Data &B) {
if(A.cnt==B.cnt) return A.id<B.id?A:B;
return A.cnt>B.cnt?A:B;
}
};
class SegmentTree {
private:
int siz;
struct node {
Data data;
int ls,rs;
node() { data=Data(),ls=rs=0; }
} tree[MAXN*50];
inline void pushup(int pos) {
tree[pos].data=tree[tree[pos].ls].data+tree[tree[pos].rs].data;
}
public:
SegmentTree() { siz=0; }
inline void Insert(int u,int l,int r,int &pos) {
if(!pos) pos=++siz;
if(l==r) {
++tree[pos].data.cnt;
tree[pos].data.id=l;
return ;
}
int mid=(l+r)>>1;
if(u<=mid) Insert(u,l,mid,tree[pos].ls);
if(mid<u) Insert(u,mid+1,r,tree[pos].rs);
pushup(pos);
}
inline int Merge(int l,int r,int des,int src) {
if(!des||!src) { return des+src; }
int id=++siz;
if(l==r) {
tree[id].data.cnt=tree[des].data.cnt+tree[src].data.cnt;
tree[id].data.id=tree[des].data.id;
return id;
}
int mid=(l+r)>>1;
tree[id].ls=Merge(l,mid,tree[des].ls,tree[src].ls);
tree[id].rs=Merge(mid+1,r,tree[des].rs,tree[src].rs);
pushup(id);
return id;
}
inline Data Query(int ul,int ur,int l,int r,int pos) {
if(!pos) return Data(0,l);
if(ul<=l&&r<=ur) return tree[pos].data;
int mid=(l+r)>>1;
if(ur<=mid) return Query(ul,ur,l,mid,tree[pos].ls);
if(mid<ul) return Query(ul,ur,mid+1,r,tree[pos].rs);
return Query(ul,ur,l,mid,tree[pos].ls)+Query(ul,ur,mid+1,r,tree[pos].rs);
}
} TR;
int n,q;
int root[MAXN<<1],fa[MAXN<<1][22];
int endpos[MAXN];
vector <int> G[MAXN<<1];
class ExSAM {
public:
struct node {
int len,link;
map <char,int> son;
node() { len=0,link=0; son.clear(); }
} st[MAXN<<1];
int siz; ExSAM() { siz=1; }
private:
inline int newch(int lst,char c) {
int cur=st[lst].son[c];
if(st[cur].len) return cur;
st[cur].len=st[lst].len+1;
int p=st[lst].link;
while(p&&st[p].son.find(c)==st[p].son.end()) {
st[p].son[c]=cur;
p=st[p].link;
}
if(!p) st[cur].link=1;
else {
int q=st[p].son[c];
if(st[q].len==st[p].len+1) st[cur].link=q;
else {
int r=++siz;
st[r].link=st[q].link,st[r].len=st[p].len+1;
for(auto e:st[q].son) if(st[e.second].len) st[r].son.insert(e);
st[q].link=st[cur].link=r;
while(p&&st[p].son[c]==q) {
st[p].son[c]=r;
p=st[p].link;
}
}
}
return cur;
}
public:
inline void insert(int id,const string &str) {
int pos=1;
for(int i=0;i<(int)str.length();++i) {
char c=str[i];
if(st[pos].son.find(c)==st[pos].son.end()) st[pos].son[c]=++siz;
pos=st[pos].son[c];
if(id) TR.Insert(id,1,n,root[pos]);
else endpos[i+1]=pos;
}
}
inline void build() {
queue <pair<int,char> > Q;
for(auto e:st[1].son) Q.push(make_pair(1,e.first));
while(!Q.empty()) {
int lst=newch(Q.front().first,Q.front().second);
Q.pop();
for(auto e:st[lst].son) Q.push(make_pair(lst,e.first));
}
}
inline void init() {
for(int i=2;i<=siz;++i) G[st[i].link].push_back(i);
auto dfs=[&](auto self,int p) -> void {
for(int v:G[p]) {
self(self,v);
root[p]=TR.Merge(1,n,root[p],root[v]);
}
};
dfs(dfs,1);
for(int i=1;i<=siz;++i) fa[i][0]=st[i].link;
for(int k=1;k<=21;++k) {
for(int i=1;i<=siz;++i) {
fa[i][k]=fa[fa[i][k-1]][k-1];
}
}
}
} SAM;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
string S;
cin>>S>>n;
SAM.insert(0,S);
for(int i=1;i<=n;++i) {
string str;
cin>>str;
SAM.insert(i,str);
}
SAM.build(),SAM.init();
cin>>q;
while(q--) {
int L,R,l,r;
cin>>L>>R>>l>>r;
int u=endpos[r];
for(int k=21;k>=0;--k) {
if(SAM.st[fa[u][k]].len>=r-l+1) u=fa[u][k];
}
auto ans=TR.Query(L,R,1,n,root[u]);
if(ans.cnt==0) ans.id=L;
cout<<ans.id<<" "<<ans.cnt<<"\n";
}
return 0;
}
