理性愉悦一下
前置知识：基本子串结构，SAM的结构和应用
学长博客
字符串理论比较抽象，建议直观的去理解它
子串$t$的扩展串定义为$\text{ext(t)}:=t'$，满足$t$是$t'$的子串，且$\text{occ(t)}=\text{occ(t')}$
基本性质：若$t=[l:r],t'=[l':r']$，$t''=[l'':r'']$，使得$l'\le l''\le l\le r\le r''\le r'$，则$\text{ext(t'')}=t'$
子串$x,y$等价当且仅当$\text{ext(x)}=\text{ext(y)}$。然后，记录每个等价类的最长串作为代表元。
在$s[l:r]\mapsto (l,r)$的作用下，在$y=x$以上的点被等价类划分入若干个阶梯状集合，其中$\text{g}$对应的阶梯 出现次数 为$\text{occ(\text{rep(g)})}$。
对于等价类$g$个某个 完整阶梯，其完整的一行对应的子串集合与$T_0$的某个结点对应的子串集合相同，其完整的一列对应的子串集合与$T_1$（反串对应的后缀树）某个节点对应的子串集合相同，并且一一对应。
定义等价类$g$的周长为其 一个 完整阶梯的行数列数之和，性质：$\sum_g\text{per(g)}=O(n)$
比较抽象。不是很直观。
如何显式求出这个结构？
第一种方式：对于$T_0$的从父亲到儿子的树边，其从一行的左边界指向另一行的右边界；对于$T_1$的从父亲到儿子的树边，其从一行的上边界连向另一行的下边界。
例如，$s=\underline{\text{aababcd}}$，其对应的阶梯划分为：
其对应的$SAM$和$T_0$为：
其对应的连边为：
第二种方式（感觉更常用）：对于$DAG$上的一条边$(u,v)$，如果$\text{occ(u)}=\text{occ(v)}$，那么就将这条边标记为关键边。
性质：如果只保留关键边，那么每个点入度和出度都至多为一，因此我们得到了若干条关键链。显然，链的末尾就是代表元，一条链就代表了一个等价类
考虑这道题目在让我们干什么：可以发现一个字符串对$(b_1,b_2)$是好的当且仅当满足以下条件：
$1.1$ $b_1,b_2$在同一个等价类中
$1.2$ 设$b_1,b_2$所在等价类中的代表元为$b$，那么$b_1,b_2$在$b$中出现的位置不交，且$b_1$在$b_2$左边
这样，我们对于每个 **阶梯状物** 统计答案即可。（建议数形结合，以及把下标搞清楚）
代表元的$\text{len}$实际上表示阶梯状物左上角那个位置的横纵坐标之差。
复杂度$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=2e5+5;
struct node{
int to[26],link,len,sz;
}t[N];
int n,cur,last,tot,sz[N];
void extend(int ch){
int cur=++tot;
t[cur].len=t[last].len+1,t[cur].sz=1;
int p=last;
while(p!=-1&&!t[p].to[ch]){
t[p].to[ch]=cur;
p=t[p].link;
}
if(p!=-1){
int q=t[p].to[ch];
if(t[q].len==t[p].len+1){
t[cur].link=q;
}
else{
int clone=++tot;
t[clone].link=t[q].link;
for(int i=0;i<26;i++)t[clone].to[i]=t[q].to[i];
t[clone].len=t[p].len+1;
while(p!=-1&&t[p].to[ch]==q){
t[p].to[ch]=clone;
p=t[p].link;
}
t[q].link=t[cur].link=clone;
}
}
last=cur;
}
string str;
int nxt[N],vs[N];
int st[N],cnt;
ll s[N];
ll res;
vector<int>G[N];
void dfs(int u){
for(auto v:G[u])dfs(v),t[u].sz+=t[v].sz;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
t[0].link=-1;cin>>str,n=str.size();
for(int i=0;i<n;i++)extend(str[i]-'a');
for(int i=1;i<=tot;i++)G[t[i].link].pb(i);
dfs(0);
for(int i=1;i<=tot;i++){
for(int j=0;j<26;j++){
int k=t[i].to[j];
if(k&&t[i].sz==t[k].sz)nxt[i]=k,vs[k]=1;
}
}
for(int i=1;i<=tot;i++){
if(vs[i]==0){
cnt=0;int e=0;
for(int j=i;j;j=nxt[j])e=j,st[++cnt]=t[j].len-t[t[j].link].len;
for(int j=1;j<=cnt;j++)s[j]=s[j-1]+st[j];
int p=1,len=t[e].len;
for(int j=len-cnt+1;j<=st[cnt]&&j<=len+1;j++){
while(p<=cnt&&st[p]<j)p++;
res+=s[cnt-len+j-1]*(cnt-p+1);
}
}
}cout<<res;
}
|