后缀数组学习笔记
xtx1092515503
2020-07-25 19:31:53
**upd：已将SA和SAM分开，现在这里是单独的SA学习笔记。**
后缀数组（SA），是一种~~非常强大~~非常令人迷惑的数据结构。这里是一份关于它的学习笔记。
这里不会讲解它的基础芝士~~因为那玩意写起来太烦人了~~，而是着重于它的应用，类似于一份题单。
一些定义：
$sa$数组：将后缀排序后排在第$i$位的后缀是谁；
$rk$数组：将后缀排序后第$i$个后缀的排名是多少；
$ht$数组：后缀数组中相邻两后缀（$i$与$i-1$）的LCP（最长公共前缀）长度。
现在开始！
# I.[不同子串个数](https://www.luogu.com.cn/problem/P2408)
后缀数组在处理**子串**问题时往往有奇效，因为**后缀的前缀即是子串**，而后缀数组正是按照**前缀排序的后缀**。
回到本题。因为后缀的前缀是子串，则一条后缀**与其它所有后缀的LCP的最长长度**，即是这条后缀的前缀子串中所有被重复计数的串的数量。
我们掏出求得的$ht$数组。初学SA时大家一定接触过一个重要的$\text{LCP Lemma}$，即$\operatorname{LCP}(i,j)=\min\limits_{i\leq j\leq k}ht_j$。我们考虑当前后缀与其它任何一条串的LCP，发现它的表达式都包含$ht_i$，即$ht_i$即为LCP的最长长度。则只需要求出所有子串数量减去$\sum\limits_{i=1}^{n}ht_i$即可。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll res;
int n,m,sa[1001000],rk[1001000],buc[1001000],x[1001000],y[1001000],ht[1001000];
char s[1001000];
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=1;
num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num==n)break;
m=num;
}
}
void HT(){
for(int i=1;i<=n;i++)rk[sa[i]]=i;
int k=0;
for(int i=1;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
int main(){
scanf("%d%s",&n,s+1),m='z';
SA(),HT();
// for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
for(int i=1;i<=n;i++)res+=(n-sa[i]+1)-ht[i];
printf("%lld\n",res);
return 0;
}
```
# II.[[USACO5.1]乐曲主题Musical Themes](https://www.luogu.com.cn/problem/P2743)
一个显然的思路就是**差分**，这样子在**原数组中差相等**，就转为**差分数组中子串相同**。
我们考虑建出后缀数组。
显然，这个答案可以二分，则我们二分一个长度$ip$。
考虑$ht$数组。我们在所有$ht_i<ip$的地方切一刀，将$ht$数组切成多段，使得每段中**除了第一个数，其它的$ht_i$全都**$\geq ip$。
显然，每段内部中任意两个串的$\operatorname{LCP}$的长度全都$\geq ip$，即以它们开头$ip$个字符构成的字符串必定相等。
因此只要它们之间不会出现重叠，即存在一组$|sa_i-sa_j|>ip$时，关于$ip$的答案就是合法的。
因此直接二分即可。复杂度$O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,s[5010],x[5010],y[5010],buc[5010],sa[5010],ht[5010],rk[5010];
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y),x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
bool che(int ip){
for(int i=2,j=2;i<=n;i=j){
int mn=sa[i],mx=sa[i];
j=i+1;
while(ht[j]>=ip)mn=min(mn,sa[j]),mx=max(mx,sa[j]),j++;
if(mx-mn>ip)return true;
}
return false;
}
int main(){
scanf("%d",&n),n--;
for(int i=0;i<=n;i++)scanf("%d",&s[i]);
for(int i=n;i;i--)s[i]-=s[i-1];
for(int i=1;i<=n;i++)s[i]+=88;//add 88 to make it positive, then we can bucket sort it more easily.
m=200;
SA();
int l=0,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(che(mid))l=mid;
else r=mid-1;
}
l++;
printf("%d\n",l<5?0:l);
return 0;
}
```
# III.[[USACO06DEC]Milk Patterns G](https://www.luogu.com.cn/problem/P2852)
同上一题思路类似，我们仍然建出后缀数组。
考虑任何出现$k$次的子串，以它们作为前缀的后缀在$sa$数组中一定是连续的——这一点可以从上文中的$\text{LCP Lemma}$直接看出，因为相邻的结果一定大于等于不相邻的结果。
因此我们只需要求出$ht$数组中相邻$k-1$个数的$\min$的最大值。直接使用滑动窗口解决即可。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,p,m,s[20100],sa[20100],rk[20100],ht[20100],x[20100],y[20100],buc[20100],res;
vector<int>v;
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y),x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
deque<int>q;
int main(){
scanf("%d%d",&n,&p),p--;
for(int i=1;i<=n;i++)scanf("%d",&s[i]),v.push_back(s[i]);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)s[i]=lower_bound(v.begin(),v.end(),s[i])-v.begin()+1;
m=v.size();
SA();
// for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",ht[i]);puts("");
for(int i=1;i<=n;i++){
while(!q.empty()&&i-q.front()>=p)q.pop_front();
while(!q.empty()&&ht[q.back()]>ht[i])q.pop_back();
q.push_back(i);
if(i>=p)res=max(res,ht[q.front()]);
}
printf("%d\n",res);
return 0;
}
```
# IV.[[POI2000]公共串](https://www.luogu.com.cn/problem/P5546)
后缀数组如何应对多个串的情况呢？
答案很简单：**把所有串都拼起来**！
但这又有个问题，拼起来的串不会出现一些错误吗？
没关系，这里就有解决方案了：**在相邻的串间插入一个从未出现过的字符**。
我们考虑在拼起来的字符串中求出$ht$数组。则仍然考虑二分公共子串长度$ip$，在$ht$数组里面按照$ht_x<ip$的位置分段。然后，如果有一段内部包含了来自所有串的后缀，则当前二分值合法；否则，则不合法。
当然这里还有一种不需要二分的方法，即用```two-pointers```求出所有出现所有串的区间，并对于每个区间求出内部所有$ht_x$的$\min$（可以用单调队列），对每个区间的结果求$\max$即可。但是因为这个方法省略不了后缀数组的$\log$（除非你用神奇的DC3），所以复杂度仍为$O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int all,n,m,x[200100],y[200100],buc[200100],sa[200100],ht[200100],rk[200100],id[200100],s[200100];
bool occ[200100];
char str[200100];
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
bool che(int ip){
for(int i=0,j=0;i<n;i=j){
if(id[sa[i]]==-1){j++;continue;}
int k=0;
k+=!occ[id[sa[i]]],occ[id[sa[i]]]=true;
for(j=i+1;j<n&&ht[j]>=ip;j++)k+=!occ[id[sa[j]]],occ[id[sa[j]]]=true;
for(int l=i;l<j;l++)occ[id[sa[l]]]=false;
if(k==all)return true;
}
return false;
}
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",str);
m=strlen(str);
for(int j=0;j<m;j++)id[n]=i,s[n]=(int)str[j]+5,n++;
id[n]=-1,s[n]=i,n++;
}
m='z'+5;
SA();
// for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
int l=0,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(che(mid))l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}
```
# V.[UVA11107 Life Forms](https://www.luogu.com.cn/problem/UVA11107)
这题同上题类似，只不过把“在全部串中出现”变成了“在超过一半（即$\left\lfloor\dfrac{n}{2}\right\rfloor+1$）个串中出现”。
这题中我的方法是上题中提到的“```two-pointers```+单调队列”算法。第一遍跑求出所有满足“出现次数”为$\left\lfloor\dfrac{n}{2}\right\rfloor+1$的**极小区间**，因为小区间的$\min ht_i$肯定大于大区间的。
在单调队列求出公共子串长度的最大值后，需要通过**关于$<ans$的位置分段**（即二分中check的方法）来输出答案——因为按照上面的单调队列算法某些子串有可能会被重复输出。
复杂度$O(n)$，假如你用DC3算法的话~~可惜我不会~~。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int all,n,m,x[200100],y[200100],buc[200100],sa[200100],ht[200100],rk[200100],id[200100],s[200100],occ[200100];
char str[200100];
void SA(){
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
deque<int>q;
int main(){
scanf("%d",&all);
while(all){
n=0;
for(int i=1;i<=all;i++){
scanf("%s",str);
m=strlen(str);
for(int j=0;j<m;j++)id[n]=i,s[n]=(int)str[j]+5,n++;
id[n]=-1,s[n]=i,n++;
}
m='z'+5;
SA();
// for(int i=0;i<n;i++)printf("%2d ",id[sa[i]]);puts("");
// for(int i=0;i<n;i++)printf("%2d ",ht[i]);puts("");
int res=0;
for(int i=0,j=0,k=0;i<n;i++){
while(j<n&&k<all/2+1){
if(id[sa[j]]!=-1)k+=!occ[id[sa[j]]]++;
while(!q.empty()&&ht[q.back()]>=ht[j])q.pop_back();
q.push_back(j++);
}
while(!q.empty()&&q.front()<=i)q.pop_front();
if(k>=all/2+1)res=max(res,ht[q.front()]);
if(id[sa[i]]!=-1)k-=!--occ[id[sa[i]]];
}
if(!res)puts("?");
else for(int i=0,j=0;i<n;i=j){
if(id[sa[i]]==-1){j++;continue;}
int k=0;
k+=!occ[id[sa[i]]],occ[id[sa[i]]]=true;
for(j=i+1;j<n&&ht[j]>=res;j++)k+=!occ[id[sa[j]]],occ[id[sa[j]]]=true;
for(int l=i;l<j;l++)occ[id[sa[l]]]=false;
if(k>=all/2+1){for(int l=0;l<res;l++)printf("%c",s[sa[i]+l]-5);puts("");}
}
for(int i=0;i<n;i++)s[i]=sa[i]=ht[i]=rk[i]=x[i]=y[i]=id[i]=0;
scanf("%d",&all);
if(all)puts("");
}
return 0;
}
```
# VI.[[AHOI2013]差异](https://www.luogu.com.cn/problem/P4248)
$\sum\limits_{1\leq i<j\leq n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{LCP}(T_i,T_j)$
这个柿子可以拆成两部分，即
$\sum\limits_{1\leq i<j\leq n}\text{len}(T_i)+\text{len}(T_j)-2\sum\limits_{1\leq i<j\leq n}\text{LCP}(T_i,T_j)$
前一半很好求，就是$\dfrac{n(n+1)(n-1)}{2}$，关键是后一半。
依据$\text{LCP Lemma}$，$\operatorname{LCP}(i,j)=\min\limits_{i\leq j\leq k}ht_j$，即区间最小值。
我们考虑求出$ht$数组。考虑每个$ht_i$会对多少个区间做出贡献（成为多少个区间的$\min$）。这是经典的**单调栈**问题，可以参见[玉蟾宫](https://www.luogu.com.cn/problem/P4147)。
复杂度$O(n)$，假如你使用DC3的话。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,x[500100],y[500100],sa[500100],ht[500100],rk[500100],buc[500100],stk[500100],tp,L[500100],R[500100];
char s[500100];
ll res;
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int main(){
scanf("%s",s),n=strlen(s),m='z';
SA();
res=1ll*n*(n+1)*(n-1)/2;
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>=ht[i])R[stk[tp--]]=i;
L[i]=stk[tp],stk[++tp]=i;
}
// for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
while(tp)R[stk[tp--]]=n;
for(int i=1;i<n;i++)res-=2ll*(i-L[i])*(R[i]-i)*ht[i];
printf("%lld\n",res);
return 0;
}
```
# VII.[[HAOI2016]找相同字符](https://www.luogu.com.cn/problem/P3181)
第一道自己做出的SA题祭~~~
实际上和上一题没啥区别的说……
我们发现，这题实际上就是对于两个串中所有的后缀求$\operatorname{LCP}$之和（因为这两个后缀共有$\operatorname{LCP}$个前缀是相同的，即串中有这么多子串是相同的）。
老套路，俩串中间插个字符怼一起，求个$ht$数组。记录个前缀和，$s1_i$表示前$i$个字符有多少个来自串一，$s2_i$表示前$i$个字符有多少来自串二，然后仍然跑单调栈，算出所有来自不同串的后缀对数量，乘上$ht$求和即可。
关键代码：
```cpp
for(int i=1;i<n;i++)res+=(1ll*(s1[i-1]-s1[L[i]-1])*(s2[R[i]-1]-s2[i-1])+1ll*(s2[i-1]-s2[L[i]-1])*(s1[R[i]-1]-s1[i-1]))*ht[i];
```
复杂度$O(n)$，假如你用DC3的话。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p;
int x[400100],y[400100],sa[400100],ht[400100],rk[400100],buc[400100];
int stk[400100],tp,L[400100],R[400100];
int s1[400100],s2[400100];
char s[400100];
ll res;
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int main(){
scanf("%s",s),p=strlen(s),s[p]=' ',scanf("%s",s+p+1),n=strlen(s),m='z';
// printf("%s\n",s);
SA();
for(int i=1;i<n;i++)s1[i]=s1[i-1]+(sa[i]<p),s2[i]=s2[i-1]+(sa[i]>p);
// for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
// for(int i=0;i<n;i++)printf("(%d,%d)",s1[i],s2[i]);puts("");
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>=ht[i])R[stk[tp--]]=i;
L[i]=stk[tp],stk[++tp]=i;
}
// for(int i=0;i<n;i++)printf("%d ",rk[i]);puts("");
while(tp)R[stk[tp--]]=n;
// for(int i=1;i<n;i++)printf("%d:(%d,%d):%d\n",i,L[i],R[i],ht[i]);
for(int i=1;i<n;i++)res+=(1ll*(s1[i-1]-s1[L[i]-1])*(s2[R[i]-1]-s2[i-1])+1ll*(s2[i-1]-s2[L[i]-1])*(s1[R[i]-1]-s1[i-1]))*ht[i];
printf("%lld\n",res);
return 0;
}
```
# VIII.[[SDOI2008]Sandy的卡片](https://www.luogu.com.cn/problem/P2463)
……有什么意义吗……
差个分，然后就是IV.[[POI2000]公共串](https://www.luogu.com.cn/problem/P5546)的内容了，套个单调队列，$O(n)$解决，假如你用DC3的话。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int all,n,m,s[200100],id[200100],x[200100],y[200100],buc[200100],sa[200100],ht[200100],rk[200100],res,occ[200100];
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
deque<int>q;
int main(){
scanf("%d",&all);
for(int i=1,x;i<=all;i++){
scanf("%d",&m),m--;
for(int j=0;j<=m;j++)scanf("%d",&s[n+j]);
for(int j=m;j;j--)s[n+j]-=s[n+j-1],s[n+j]+=10000,id[n+j]=i;
s[n]=i-1,n+=m,n++;
}
n--,m=20000;
// for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
SA();
// for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",id[i]);puts("");
for(int i=1,j=1,k=0;i<=n;i++){
while(j<=n&&k<all){
if(id[sa[j]])k+=!occ[id[sa[j]]]++;
while(!q.empty()&&ht[q.back()]>=ht[j])q.pop_back();
q.push_back(j++);
}
while(!q.empty()&&q.front()<=i)q.pop_front();
if(k==all)res=max(res,ht[q.front()]);
if(id[sa[i]])k-=!--occ[id[sa[i]]];
}
printf("%d\n",res+1);
return 0;
}
```
# IX.[[JSOI2007]字符加密](https://www.luogu.com.cn/problem/P4051)
这题的思路非常简单——断环复制成链，然后直接后缀排序一下即可。
为什么呢？
我们考虑两条后缀。假如它们在前$n$位中有所不同，显然它们之间的相对顺序不会有问题；
否则，假如它们前$n$位全都相同，则因为反正最后输出的就是最后一个字符，所以相对顺序没有影响，直接按照更往后的东西决定顺序也没有问题。
总复杂度$O(n)$，假如DC3。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,buc[400100],x[400100],y[400100],sa[400100];
char s[400100];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
}
int main(){
scanf("%s",s),n=strlen(s);
for(int i=0;i<n;i++)s[i+n]=s[i];
n<<=1,m='z';
// printf("%s:%d,%d\n",s,n,m);
SA();
n>>=1;
for(int i=0;i<(n<<1);i++)if(sa[i]<n)printf("%c",s[sa[i]+n-1]);
return 0;
}
```
# X.[[SCOI2012]喵星球上的点名](https://www.luogu.com.cn/problem/P2336)
我居然做出了这题……难以置信！
首先，思路很明显是把所有串全怼一起（包括名字和询问串），加上分隔符，然后跑一遍后缀数组。
我们仍然可以用单调栈求出关于每个询问串与它相同的区间。即，如果以询问串为前缀的那个后缀的$rank$是$p$的话，它的合法区间$[L,R]$应该满足$\forall L<i\leq R,ht_i\geq ht_p$。注意这里是$\geq$而非$>$，因此应该特别注意处理$=$的部分。
这里放一下求出全部$[L,R)$的代码（注意这里数组中的$[L,R)$实际上是**左闭右开**的，而我们最终要求的$[L,R]$是左闭右闭的，所以接下来用的时候$R$要减去$1$）：
```cpp
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
else L[i]=stk[tp];
stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
```
求出所有合法的$[L,R]$后，我们可以考虑那两个询问了。
首先，对于第一问，发现它就是求区间$[L,R]$内部所有**出现过的姓名串**的数量。这不就是[[SDOI2009]HH的项链](https://www.luogu.com.cn/problem/P1972)吗？树状数组即可。~~当然你要真想写莫队也没人拦得住你~~。
然后，关于第二问，它的意义实际上是将区间$[L,R]$内部所有出现过的姓名串的**计数器**增加$1$。如果关于询问串下手我们没有办法，但是我们可以关于姓名串下手呀！
我们设一个**下标**$i$，它所代表的姓名串为代码中的$id\big[sa[i]\big]$，我们这里设一个$c_i$代表它。我们再设它之前上一个出现的该姓名串的下标为$LAS_i$（如果之前没有出现任何这个姓名串的下标，$LAS_i=-1$）。则显然，所有满足$i\in[L,R]$且$LAS_i<L$的区间$[L,R]$都可以对$c_i$有贡献。这是什么？**二维数点**问题呀！
于是我们愉快地排个序就能用线段树求出答案。
复杂度$O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int S,T,cnt,id[400100],tms[400100],ans[400100],stt[400100],P,Q,len[400100];
//-------------------Suffix Array Below--------------------
int stk[400100],tp,L[400100],R[400100];
namespace Suffix_Array{
int x[400100],y[400100],sa[400100],ht[400100],rk[400100],buc[400100],s[400100],n,m;
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
//------------------Suffix Array Above---------------------
int las[400100],LAS[400100];
//------------------Ask the Queries Below------------------
struct Query{
int l,r,id;
Query(int a=0,int b=0,int c=0){l=a,r=b,id=c;}
}q[400100];
bool cmp1(Query &u,Query &v){
return u.r<v.r;
}
int t[400100];
void add(int x,int y){
x++;
while(x<=n)t[x]+=y,x+=x&-x;
}
int sum(int x){
x++;
int ret=0;
while(x)ret+=t[x],x-=x&-x;
return ret;
}
//------------------Ask the Queries Above------------------
//-----------------Calculate the Times Below---------------
pair<int,int>p[400100];
bool cmp(pair<int,int>&u,pair<int,int>&v){//first:place second:last
return u.second>v.second;
}
bool cmp2(Query &u,Query &v){
return u.l>v.l;
}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
int tag[1600100];
void pushdown(int x){tag[lson]+=tag[x],tag[rson]+=tag[x],tag[x]=0;}
void modify(int x,int l,int r,int L,int R){
if(l>R||r<L)return;
if(L<=l&&r<=R){tag[x]++;return;}
pushdown(x),modify(lson,l,mid,L,R),modify(rson,mid+1,r,L,R);
}
int query(int x,int l,int r,int P){
if(l>P||r<P)return 0;
if(l==r)return tag[x];
pushdown(x);
return query(lson,l,mid,P)+query(rson,mid+1,r,P);
}
#undef lson
#undef rson
#undef mid
//----------------------Calculate the Times Above----------
int main(){
scanf("%d%d",&S,&T),cnt=10000;
for(int i=1;i<=S;i++){
scanf("%d",&m);
for(int j=0;j<m;j++)scanf("%d",&s[n+j]),id[n+j]=i;
n+=m;
s[n++]=++cnt;
scanf("%d",&m);
for(int j=0;j<m;j++)scanf("%d",&s[n+j]),id[n+j]=i;
n+=m;
s[n++]=++cnt;
}
for(int i=1;i<=T;i++){
scanf("%d",&m),stt[i]=n;
len[i]=m;
for(int j=0;j<m;j++)scanf("%d",&s[n+j]),id[n+j]=S+i;
n+=m;
s[n++]=++cnt;
}
m=cnt;
SA();
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[stk[tp--]]=i;
if(ht[stk[tp]]==ht[i])L[i]=L[stk[tp]];
else L[i]=stk[tp];
stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
for(int i=1;i<=T;i++)if(ht[rk[stt[i]]]==len[i])q[++Q]=Query(L[rk[stt[i]]],R[rk[stt[i]]]-1,i);
// for(int i=0;i<n;i++)printf("%2d::S:%5d id:%d rk:%2d sa:%2d ht:%d\n",i,s[i],id[i],rk[i],sa[i],ht[i]);
// for(int i=1;i<=T;i++)printf("%d %d\n",q[i].l,q[i].r);
sort(q+1,q+Q+1,cmp1),memset(las,-1,sizeof(las));
for(int i=1,j=0;i<=Q;i++){
for(;j<=q[i].r;j++){
if(id[sa[j]]>S||!id[sa[j]])continue;
LAS[j]=las[id[sa[j]]],las[id[sa[j]]]=j;
if(LAS[j]!=-1)add(LAS[j],-1);
add(j,1);
p[++P]=make_pair(j,LAS[j]);
}
ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
}
for(int i=1;i<=T;i++)printf("%d\n",ans[i]);
sort(q+1,q+Q+1,cmp2),sort(p+1,p+P+1,cmp);
for(int i=1,j=1;i<=P;i++){
while(j<=Q&&p[i].second<q[j].l)modify(1,0,n-1,q[j].l,q[j].r),j++;
tms[id[sa[p[i].first]]]+=query(1,0,n-1,p[i].first);
}
for(int i=1;i<=S;i++)printf("%d ",tms[i]);
return 0;
}
```
# XI.[[APIO2014]回文串](https://www.luogu.com.cn/problem/P3649)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-p3649)
# XII.[[TJOI2015]弦论](https://www.luogu.com.cn/problem/P3975)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-p3975)
# XIII.[[BJWC2010]外星联络](https://www.luogu.com.cn/problem/P4341)
和上题一样，没啥好说的，直接建出笛卡尔树即可。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int stk[500100],tp,L[500100],R[500100],id,pt;
namespace Suffix_Array{
const int N=500100;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
int mn[500100][20],LG[500100];
int MIN(int i,int j){
return ht[i]<=ht[j]?i:j;
}
int RMQ(int l,int r){
int k=LG[r-l+1];
return MIN(mn[l][k],mn[r-(1<<k)+1][k]);
}
void solve(int l,int r,int las){
// printf("%d %d %d\n",l,r,las);
if(l>r)return;
int mp=RMQ(l,r);
for(int j=las;j<ht[mp];j++)printf("%d\n",r-l+2);
solve(l,mp-1,ht[mp]),solve(mp+1,r,ht[mp]);
}
int main(){
scanf("%d%s",&n,s),m='1';
SA();
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=i;
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=MIN(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
solve(1,n-1,0);
return 0;
}
/*
aabbababb
1 12
*/
```
# XIV.[[SDOI2016]生成魔咒](https://www.luogu.com.cn/problem/P4070)
动态SA？这怎么办？
我们考虑往每个后缀后面全都加入一个数。很明显，如果这样搞的话，你必须每加入一个数后都要重新后缀排序，不太可能完成。
这时，我们发现，如果这不是加入一个数，而是加入**一整条后缀**，那就会轻松很多，一个平衡树就能搞定。
思考后会发现，如果我们将整个串翻转，则原本是加入一个数，现在则变成了加入一条后缀！并且，翻转对答案并无影响——毕竟本质不同子串数无论正着来还是反着来都是一样的。
当你加入一条后缀时，所有新增加的子串数量，就等于$n-i-\max\limits_{j>i}\{\operatorname{LCP}(i,j)\}$。
应用$\text{LCP Lemma}$，我们知道$\operatorname{LCP}(i,j)=\min\limits_{rk_i<k\leq rk_j}ht_k$
则显然，只有$rk_i$左右侧的$rk_j$才会是最大值。于是我们就可以用一个```std::set```来维护所有的$rk_j$，记为$\mathbb{S}$。则每加入一个数，就在$\mathbb{S}$中二分到前后的$rk_j$然后求$\operatorname{LCP}$即可。
复杂度$O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace Suffix_Array{
const int N=100100;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m,s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
int mn[100100][20],LG[100100];
int LCP(int l,int r){//get the LCP of suffix l and r;
l++;
int k=LG[r-l+1];
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
vector<int>v;
set<int>st;
ll res;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&s[i]),v.push_back(s[i]);
sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
for(int i=0;i<n;i++)s[i]=lower_bound(v.begin(),v.end(),s[i])-v.begin()+1;
reverse(s,s+n);
SA();
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
for(int i=n-1;i>=0;i--){
int sm=0;
auto it=st.upper_bound(rk[i]);
if(it!=st.end())sm=max(sm,LCP(rk[i],*it));
if(it!=st.begin())it--,sm=max(sm,LCP(*it,rk[i]));
st.insert(rk[i]);
res+=n-i-sm;
printf("%lld\n",res);
}
return 0;
}
```
# XV.[Annihilate](https://www.luogu.com.cn/problem/P5028)
~~我当年为什么会手贱开这卡常大毒瘤题呀~~
思路1. 用```vector```存下每个字符串在后缀排序后的下标，然后每次枚举两个串，用一个```vector```里面的数在另一个里面```two-pointers```找到它两侧的数，然后用ST表求LCP。
时间复杂度$O\Big(\sum|S|(\log\sum|S|+n^2)\Big)$，空间复杂度$O(n\log n)$，光荣MLE。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int all,id[1001000],res[100][100];
namespace Suffix_Array{
const int N=1001000;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
vector<int>v[60];
int mn[1001000][20],LG[1001000];
int LCP(int l,int r){//get the LCP of suffix l and r;
l++;
int k=LG[r-l+1];
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",s+n);
m=strlen(s+n);
for(int j=n;j<n+m;j++)id[j]=i;
n+=m;
s[n++]=i;
}
m='z';
SA();
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
for(int i=0;i<n;i++)if(id[sa[i]])v[id[sa[i]]].push_back(i);
for(int i=1;i<=all;i++)for(int j=i+1;j<=all;j++){
for(int a=0,b=0;a<v[i].size();a++){
while(b<v[j].size()&&v[i][a]>v[j][b])b++;
if(b<v[j].size())res[i][j]=max(res[i][j],LCP(v[i][a],v[j][b]));
if(b)res[i][j]=max(res[i][j],LCP(v[j][b-1],v[i][a]));
}
}
for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",res[min(i,j)][max(i,j)]);puts("");}
return 0;
}
```
思路2. 用单调队列求LCP
大体思路和上题一致，只不过换用单调队列求LCP。
时间复杂度$O\Big(\sum|S|(\log\sum|S|+n^2)\Big)$，光荣TLE。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int all,id[1001000],res[100][100];
namespace Suffix_Array{
const int N=1001000;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m;
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i],y[i]=0;
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<n&&i+k<n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
vector<int>v[60];
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",s+n);
m=strlen(s+n);
for(int j=n;j<n+m;j++)id[j]=i;
n+=m;
s[n++]=i;
}
m='z';
SA();
for(int i=1;i<=all;i++)v[i].push_back(i);
for(int i=0;i<n;i++)if(id[sa[i]])v[id[sa[i]]].push_back(i);
for(int i=1;i<=all;i++)for(int j=i+1;j<=all;j++){
deque<int>p,q;
for(int a=1,b=0;a<v[i].size();a++){
for(int k=v[i][a-1]+1;k<=v[i][a];k++){
while(!p.empty()&&ht[p.back()]>=ht[k])p.pop_back();
p.push_back(k);
}
while(b<v[j].size()&&v[i][a]>v[j][b]){
while(!p.empty()&&p.front()<=v[j][b])p.pop_front();
b++;
if(b==v[j].size())break;
for(int k=v[j][b-1]+1;k<=v[j][b];k++){
while(!q.empty()&&ht[q.back()]>=ht[k])q.pop_back();
q.push_back(k);
}
}
while(!q.empty()&&q.front()<=v[i][a])q.pop_front();
if(!p.empty())res[i][j]=max(res[i][j],ht[p.front()]);
if(!q.empty())res[i][j]=max(res[i][j],ht[q.front()]);
}
}
for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",res[min(i,j)][max(i,j)]);puts("");}
return 0;
}
```
思路3.正解
我们设一个$las_i$表示当前位置到上一个来自$i$串的后缀的区间中的$\min ht_x$。到了每一个位置$O(n)$地遍历$las$数组更新并计算答案。复杂度$O\Big(\sum|S|\log(\sum|S|+n)\Big)$，可以通过。
但是这题卡常强烈吐槽！
代码（开O2通过）：
```cpp
#include<bits/stdc++.h>
using namespace std;
int all,id[1010000],res[100][100],las[100];
namespace Suffix_Array{
const int N=1010000;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N],n,m,s[N];
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num>=n)break;
m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
char str[1001000];
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",str);
m=strlen(str);
for(int j=0;j<m;j++)n++,s[n]=str[j]-'a'+1,id[n]=i;
s[++n]=i+26;
}
m=all+26;
SA();
// for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
for(int i=2;i<=n;i++){
for(int j=1;j<=all;j++)las[j]=min(las[j],ht[i]);
las[id[sa[i-1]]]=ht[i];
for(int j=1;j<=all;j++)res[j][id[sa[i]]]=max(res[j][id[sa[i]]],las[j]);
}
for(int i=1;i<=all;i++){for(int j=1;j<=all;j++)if(i!=j)printf("%d ",max(res[i][j],res[j][i]));puts("");}
return 0;
}
```
# XVI.[[NOI2015]品酒大会](https://www.luogu.com.cn/problem/P2178)
~~我居然能自己AC NOI的原题，后缀数组果然简单~~
首先当然是轻松建出SA。
我们考虑借鉴XII.[[TJOI2015]弦论](https://www.luogu.com.cn/problem/P3975)的思想，建出笛卡尔树。则对于当前的$ht$长度，它出现在了$(l,r)$区间里的每一个后缀里，共计$\dfrac{(r-l+2)(r-l+1)}{2}$次。同时，这份贡献会对$(ht_{(l,r)},ht_{fa})$区间中的每一个”$r$相似“全部有这么多的贡献，因此直接差个分即可。同时，这个区间内部任意两个$a_{sa_i}\times a_{sa_j}$的$\max$，要么来自于（$\text{最大}\times\text{次大}$），要么来自于（$\text{最小}\times\text{次小}$），用线段树维护即可。最后，对差分数组做后缀和，对$\max$数组求后缀$\max$即可。
复杂度$O(n\log n)$，TLE。
代码：
```cpp
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100];
int x[300100],y[300100],sa[300100],ht[300100],rk[300100],buc[300100];
char s[300100];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int LG[300100],mn[300100][20];
ll cnt[300100],mx[300100];
int MIN(int x,int y){return ht[x]<=ht[y]?x:y;}
int RMQ(int l,int r){
int k=LG[r-l+1];
return MIN(mn[l][k],mn[r-(1<<k)+1][k]);
}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{
int mx1,mx2,mn1,mn2;
SegTree(){mx1=mx2=0x80808080,mn1=mn2=0x3f3f3f3f;}
SegTree(int x){mx1=mn1=x,mx2=0x80808080,mn2=0x3f3f3f3f;}
friend SegTree operator +(const SegTree &x,const SegTree &y){
SegTree z;
vector<int>v;
v={x.mx1,x.mx2,y.mx1,y.mx2};
sort(v.begin(),v.end());
z.mx1=v[3],z.mx2=v[2];
v={x.mn1,x.mn2,y.mn1,y.mn2};
sort(v.begin(),v.end());
z.mn1=v[0],z.mn2=v[1];
return z;
}
ll calc(){
ll ret=0x8080808080808080;
if(mn1!=0x3f3f3f3f&&mn2!=0x3f3f3f3f)ret=max(ret,1ll*mn1*mn2);
if(mx1!=0x80808080&&mx2!=0x80808080)ret=max(ret,1ll*mx1*mx2);
return ret;
}
}seg[1200100];
void build(int x,int l,int r){
if(l==r){seg[x]=SegTree(a[sa[l]]);return;}
build(lson,l,mid),build(rson,mid+1,r),seg[x]=seg[lson]+seg[rson];
}
SegTree query(int x,int l,int r,int L,int R){
if(l>R||r<L)return SegTree();
if(L<=l&&r<=R)return seg[x];
return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
void solve(int l,int r,int las){
if(l>r)return;
int mp=RMQ(l,r),len=r-l+2;
cnt[ht[mp]]+=1ll*len*(len-1)/2,mx[ht[mp]]=max(mx[ht[mp]],query(1,0,n-1,l-1,r).calc());
cnt[las]-=1ll*len*(len-1)/2;
solve(l,mp-1,ht[mp]),solve(mp+1,r,ht[mp]);
}
int main(){
scanf("%d%s",&n,s),m='z',memset(mx,0x80,sizeof(mx));
for(int i=0;i<n;i++)scanf("%d",&a[i]);
SA();
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=i;
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=MIN(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
build(1,0,n-1),solve(1,n-1,-1);
for(int i=n-1;i>=0;i--)cnt[i]+=cnt[i+1],mx[i]=max(mx[i],mx[i+1]);
for(int i=0;i<n;i++)printf("%lld %lld\n",cnt[i],cnt[i]==0ll?0ll:mx[i]);
return 0;
}
```
既然如此，我们只能考虑$O(n)$地建笛卡尔树并$O(n)$维护最大次大值。
在经历多次失败后，我找出了$O(n)$建树的方法：
```cpp
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[stk[tp]]=i,lson[i]=stk[tp],tp--;
L[i]=stk[tp],rson[stk[tp]]=i,stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
rt=stk[1];
solve(rt,-1);
```
但是怎样$O(n)$维护呢？
又经过实验后，我发现这个最大次大值可以通过两个儿子的值合并算出来。如果某个儿子不存在的话，就要把对应的端点贡献算入。
这里是$O(n)$的```solve```函数：
```cpp
void solve(int x,int las){
int len=R[x]-L[x];
cnt[ht[x]]+=1ll*len*(len-1)/2;
cnt[las]-=1ll*len*(len-1)/2;
if(lson[x])solve(lson[x],ht[x]),dat[x]+=dat[lson[x]];
else dat[x]+=Data(a[sa[L[x]]]);
if(rson[x])solve(rson[x],ht[x]),dat[x]+=dat[rson[x]];
else dat[x]+=Data(a[sa[R[x]-1]]);
mx[ht[x]]=max(mx[ht[x]],dat[x].calc());
}
```
其中```dat[x]```是一个类型为```Data```的```struct```，已经提前定义了加法，可以维护最大次大值。
总复杂度$O(n\log n)$，瓶颈为后缀排序，采用DC3算法即可优化到整体$O(n)$。但是不使用DC3仍然可以通过。
代码：
```cpp
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100];
int x[300100],y[300100],sa[300100],ht[300100],rk[300100],buc[300100];
char s[300100];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
struct Data{
int mx1,mx2,mn1,mn2;
Data(){mx1=mx2=0x80808080,mn1=mn2=0x3f3f3f3f;}
Data(int x){mx1=mn1=x,mx2=0x80808080,mn2=0x3f3f3f3f;}
void Print()const{
printf("%d %d %d %d\n",mx1,mx2,mn1,mn2);
}
void operator +=(const Data&x){
if(x.mx1>=mx1)mx2=max(mx1,x.mx2),mx1=x.mx1;
else mx2=max(mx2,x.mx1);
if(x.mn1<=mn1)mn2=min(mn1,x.mn2),mn1=x.mn1;
else mn2=min(mn2,x.mn1);
}
ll calc(){
ll ret=0x8080808080808080;
if(mn1!=0x3f3f3f3f&&mn2!=0x3f3f3f3f)ret=max(ret,1ll*mn1*mn2);
if(mx1!=0x80808080&&mx2!=0x80808080)ret=max(ret,1ll*mx1*mx2);
return ret;
}
}dat[300100];
int stk[300100],tp,lson[300100],rson[300100],L[300100],R[300100],rt;
ll cnt[300100],mx[300100];
void solve(int x,int las){
int len=R[x]-L[x];
cnt[ht[x]]+=1ll*len*(len-1)/2;
cnt[las]-=1ll*len*(len-1)/2;
if(lson[x])solve(lson[x],ht[x]),dat[x]+=dat[lson[x]];
else dat[x]+=Data(a[sa[L[x]]]);
if(rson[x])solve(rson[x],ht[x]),dat[x]+=dat[rson[x]];
else dat[x]+=Data(a[sa[R[x]-1]]);
// printf("%d:(%d,%d):(%d,%d):%d\n",x,L[x],R[x]-1,lson[x],rson[x],ht[x]);
// printf("%d:",x);dat[x].Print();
mx[ht[x]]=max(mx[ht[x]],dat[x].calc());
}
int main(){
scanf("%d%s",&n,s),m='z',memset(mx,0x80,sizeof(mx));
for(int i=0;i<n;i++)scanf("%d",&a[i]);
SA();
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[stk[tp]]=i,lson[i]=stk[tp],tp--;
L[i]=stk[tp],rson[stk[tp]]=i,stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
// for(int i=0;i<n;i++)printf("%d ",a[sa[i]]);puts("");
rt=stk[1];
solve(rt,-1);
for(int i=n-1;i>=0;i--)cnt[i]+=cnt[i+1],mx[i]=max(mx[i],mx[i+1]);
for(int i=0;i<n;i++)printf("%lld %lld\n",cnt[i],cnt[i]==0ll?0ll:mx[i]);
return 0;
}
```
# XVII.[[USACO17DEC]Standing Out from the Herd P](https://www.luogu.com.cn/problem/P4081)
一个naive的思路就是将所有串拼一起然后后缀排序，找出所有连续的来自同一个串的后缀。考虑结合I.[不同子串个数](https://www.luogu.com.cn/problem/P2408)思考，则如果该区间是$[l,r]$的话，它的贡献应该是$\sum\limits_{l\leq i\leq r}len_{sa_i}-\sum\limits_{l\leq i\leq r+1}ht_i$，其中$len_{sa_i}$是$i$位置的后缀的长度。注意因为这里要求在**所有串中都没有出现过**，所以$ht_i$的区间应是$[l,r+1]$，包括了前一个串和后一个串中的出现。
但是你会发现它有问题。假如你考虑极端情况，即$l=r$时，这是有重复部分的。
比如说下面举一个例子：
```aaaaaa...```
```aaaab...```
```aaac...```
这是后缀数组中三个连续的串。我们这时想要考虑中间那一个串在其他串中出现过的长度。显然，应该是```len(aaaa)=4```。
但是，两边的$ht$，一个是$4$，一个是$3$。你要两个都算的话，就算重复了。
因此我们对于上面的式子，还应该减去一个$\operatorname{LCP}(l-1,r+1)$，即正确的式子应该是$\sum\limits_{l\leq i\leq r}len_{sa_i}-\sum\limits_{l\leq i\leq r+1}ht_i+\min\limits_{l\leq i\leq r+1}ht_i$，这样才不会重复计算。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,all,id[300100],len[300100];
int x[300100],y[300100],sa[300100],ht[300100],rk[300100],buc[300100],s[300100];
ll res[300100];
char str[300100];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int main(){
scanf("%d",&all);
for(int i=1;i<=all;i++){
scanf("%s",str);
m=strlen(str);
for(int j=0;j<m;j++)len[n]=m-j,id[n]=i,s[n]=str[j]-'a'+1,n++;
s[n++]=i+26;
}
m=all+26;
SA();
// for(int i=0;i<n;i++)printf("%d ",id[sa[i]]);puts("");
// for(int i=0;i<n;i++)printf("%d ",len[sa[i]]);puts("");
// for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
for(int i=0,LCP=0;id[sa[i]];i++){
LCP=min(LCP,ht[i]),res[id[sa[i]]]+=len[sa[i]]-ht[i];
if(id[sa[i]]!=id[sa[i-1]])res[id[sa[i-1]]]-=ht[i],res[id[sa[i-1]]]+=LCP,LCP=ht[i];
}
for(int i=1;i<=all;i++)printf("%lld\n",res[i]);
return 0;
}
```
# XVIII.[[HEOI2016/TJOI2016]字符串](https://www.luogu.com.cn/problem/P4094)
作为一个理智正常的OIer，二维数点的题说什么都应该离线线段树通过而不是大力搞主席树呀（（（
我们发现这题询问中$s[c,\dots,d]$中这个“$d$”是不重要的，只需要把最终结果同$(d-c+1)$取$\min$即可，因此忽略不管。
然后这个问题就被转换成了：对于区间$[a,b]$内所有后缀$suf[i]$，求$\min\Big(\operatorname{LCP}(suf[i],suf[c]),b-i+1\Big)$的最大值。
我们考虑二分这个最大值，设为$mid$。现在要来判断$mid$这个值是否合法。则只有区间$[a,a+mid-1]$中的$\operatorname{LCP}$才可能达到这么长，故只要找到其中的$\max\text{LCP}$，如果其长度大于等于$mid$，则$mid$合法。
到现在我们已经可以构思出一个$O(n\log^2n)$的二分套线段树的做法了。具体思路是，因为$\max\text{LCP}$一定在两个后缀的$rk$最接近时取到，所以我们将它拆成两半，一半是$rk_i\leq rk_c$的，一半是$rk_i\geq rk_c$的。
则我们需要先将询问按照$rk_c$排序，按顺序将位置插入线段树，在前一半中查询区间中$rk_i$的最大值，后一半中查询$rk_i$的最小值（这里的线段树是以**原串位置**为下标的）。在查询到这个值最大值/最小值后，就可以通过ST表求出$\text{LCP}$了。当然，这一切都是建立在二分的基础上，即，我们每次询问的区间都是二分出来的区间$[a,a+mid-1]$。
但是这样子得写两棵线段树，再加上ST表，太难受了。我们不如这样，直接在线段树上维护$\text{LCP}$长度。办法很简单，当新加入一个位置后，直接将线段树中所有$\text{LCP}$长度与它取$\min$即可。
我们可以写出这样的```pushdown```函数：
```cpp
#define change(x,y) seg[x].lcp=min(seg[x].lcp,y),seg[x].tag=min(seg[x].tag,y)
void pushdown(int x){
change(lson,seg[x].tag),change(rson,seg[x].tag),seg[x].tag=0x3f3f3f3f;
}
```
然后在主函数只需要这样来一句```change(1,ht[j])```即可。
在取$\min$后，把对应位置的$\text{LCP}$长度改成$n-i$，因为自己跟自己的$\text{LCP}$长度就是串长。
这里是将一个位置插入线段树的代码：
```cpp
void turnon(int x,int l,int r,int P){
if(l>P||r<P)return;
seg[x].lcp=max(seg[x].lcp,n-P);
if(l!=r)pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P);
}
```
到这里，我们已经省掉了ST表，并且也只用写一颗线段树了。我们要不再努力努力，干脆连二分也给省了，直接在线段树上二分？
我们设一个```query```函数来回答询问。我们考虑当前走到节点$x$，它代表的区间是$[l,r]$，询问区间是$[L,R]$。
1. 假如$[l,r]\cup[L,R]=\emptyset$，直接```return -1```即可。
2. 假如$[l,r]\subseteq[L,R]$：
2.1. 如果$lcp_x\geq R-r+1$，则显然**全局**最优答案肯定处于区间$[l,r]$之中，我们单独开一个```getans```函数来处理这种情况，马上讲。我们直接返回```getans```的结果，并标记找到了答案。
2.2 否则，$lcp_x$就是**区间$[l,r]$中**的最优答案（因为没有越界），直接```return lcp[x]```即可。
3. 否则，先递归左儿子，如果左儿子找到答案，直接```return 左儿子的答案```即可；否则，```return max(左儿子的答案，右儿子的答案）```
至于```getans```函数，就是一个常规的线段树上二分，找到最小的那个满足```lcp[x]>=R-r+1```的位置并返回即可。
这部分代码：
```cpp
int getans(int x,int l,int r,int L,int R){//this function is to find the real answer in a section
if(l==r)return min(seg[x].lcp,R-r+1);//we've reached a leaf, go back immediately.
pushdown(x);
if(seg[lson].lcp>=R-mid+1)return getans(lson,l,mid,L,R);//the answer in left son is surely the best
else return max(seg[lson].lcp,getans(rson,mid+1,r,L,R));//the left answer hasn't gone over the border, so it's the real answer
}
int query(int x,int l,int r,int L,int R,bool &findans){//this function is to find the answer to the queries
if(l>R||r<L)return -1;
if(L<=l&&r<=R){
if(seg[x].lcp>=R-r+1){findans=true;return getans(x,l,r,L,R);}//the answer here is the best answer
return seg[x].lcp;//the answer has't gone over the border, so it's the real answer
}
pushdown(x);
int tmp=query(lson,l,mid,L,R,findans);
if(findans)return tmp;
return max(tmp,query(rson,mid+1,r,L,R,findans));
}
```
正着来一遍，反着再来一遍，两边答案取$\max$即可。
总复杂度$O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,q,res[N],len[N];
namespace Suffix_Array{
int x[N],y[N],sa[N],ht[N],rk[N],buc[N];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
struct Query{
int L,R,pos,id;
Query(int a=0,int b=0,int c=0,int d=0){L=a,R=b,pos=c,id=d;}
friend bool operator <(const Query&x,const Query&y){
return x.pos<y.pos;
}
}p[N];
namespace SegMentTree{
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{//lcp stands for the maximum lcp in the section
int lcp,tag;
}seg[N<<2];
#define change(x,y) seg[x].lcp=min(seg[x].lcp,y),seg[x].tag=min(seg[x].tag,y)
void pushdown(int x){
change(lson,seg[x].tag),change(rson,seg[x].tag),seg[x].tag=0x3f3f3f3f;
}
void build(int x,int l,int r){
seg[x].tag=0x3f3f3f3f,seg[x].lcp=-1;
if(l!=r)build(lson,l,mid),build(rson,mid+1,r);
}
void turnon(int x,int l,int r,int P){
if(l>P||r<P)return;
seg[x].lcp=max(seg[x].lcp,n-P);
if(l!=r)pushdown(x),turnon(lson,l,mid,P),turnon(rson,mid+1,r,P);
}
int getans(int x,int l,int r,int L,int R){//this function is to find the real answer in a section
if(l==r)return min(seg[x].lcp,R-r+1);//we've reached a leaf, go back immediately.
pushdown(x);
if(seg[lson].lcp>=R-mid+1)return getans(lson,l,mid,L,R);//the answer in left son is surely the best
else return max(seg[lson].lcp,getans(rson,mid+1,r,L,R));//the left answer hasn't gone over the border, so it's the real answer
}
int query(int x,int l,int r,int L,int R,bool &findans){//this function is to find the answer to the queries
if(l>R||r<L)return -1;
if(L<=l&&r<=R){
if(seg[x].lcp>=R-r+1){findans=true;return getans(x,l,r,L,R);}//the answer here is the best answer
return seg[x].lcp;//the answer has't gone over the border, so it's the real answer
}
pushdown(x);
int tmp=query(lson,l,mid,L,R,findans);
if(findans)return tmp;
return max(tmp,query(rson,mid+1,r,L,R,findans));
}
#undef lson
#undef rson
#undef mid
}
using namespace SegMentTree;
int main(){
scanf("%d%d%s",&n,&q,s),m='z',SA();
for(int i=1,a,b,c,d;i<=q;i++)scanf("%d%d%d%d",&a,&b,&c,&d),p[i]=Query(a-1,b-1,rk[c-1],i),len[i]=d-c+1;
sort(p+1,p+q+1);
build(1,0,n-1);
for(int i=1,j=0;i<=q;i++){
for(;j<=p[i].pos;j++)change(1,ht[j]),turnon(1,0,n-1,sa[j]);
bool tmp=false;
res[p[i].id]=max(res[p[i].id],query(1,0,n-1,p[i].L,p[i].R,tmp));
}
build(1,0,n-1);
for(int i=q,j=n-1;i;i--){
for(;j>=p[i].pos;j--)change(1,ht[j+1]),turnon(1,0,n-1,sa[j]);
bool tmp=false;
res[p[i].id]=max(res[p[i].id],query(1,0,n-1,p[i].L,p[i].R,tmp));
}
for(int i=1;i<=q;i++)printf("%d\n",min(res[i],len[i]));
return 0;
}
```
# XIX.[工艺 /【模板】最小表示法](https://www.luogu.com.cn/problem/P1368)
没啥好说的，直接倍长数组，然后后缀排序即可，道理都在IX.[[JSOI2007]字符加密](https://www.luogu.com.cn/problem/P4051)那儿讲过了。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=600100;
int n,m;
int s[N],x[N<<1],y[N<<1],buc[N],sa[N];
vector<int>v;
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i];
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(n==num)break;
m=num;
}
}
void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
read(n);
for(int i=1;i<=n;i++)read(s[i]),s[i+n]=s[i],v.push_back(s[i]);
sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
n<<=1;
for(int i=1;i<=n;i++)s[i]=lower_bound(v.begin(),v.end(),s[i])-v.begin()+1;
SA();
for(int i=1;i<=n;i++){
if(n-sa[i]+1<(n>>1))continue;
for(int j=1;j<=(n>>1);j++)printf("%d ",v[s[sa[i]+j-1]-1]);puts("");
break;
}
return 0;
}
```
# XX.[【模板】后缀自动机 (SAM)](https://www.luogu.com.cn/problem/P3804)
~~俗话说的好，模板题怎么能用模板水过去呢~~
我们考虑用建出$ht$数组，然后用**单调栈**求出每个$ht$最多能向左向右延伸多远（VI.[[AHOI2013]差异](https://www.luogu.com.cn/problem/P4248)），然后直接一边扫过求$\max$即可。
复杂度$O(n)$，假如你用DC3的话。但是用倍增实际跑起来也真的超快！！！
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1001000;
int n,m;
int x[N],y[N],sa[N],ht[N],rk[N],buc[N];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int L[N],R[N],stk[N],tp;
ll res;
int main(){
scanf("%s",s),n=strlen(s),m='z';
SA();
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])R[stk[tp]]=i,tp--;
L[i]=stk[tp],stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
for(int i=1;i<n;i++)res=max(res,1ll*ht[i]*(R[i]-L[i]));
printf("%lld\n",res);
return 0;
}
```
# XXI.[[NOI2016]优秀的拆分](https://www.luogu.com.cn/problem/P1117)
这后缀数组越来越像一个用来求$\operatorname{LCP}$的工具人了……
对于一个$\text{AABB}$的拆分，我们可以在中间切一刀，变成$\text{AA}$与$\text{BB}$两半。这时，我们只需要设$a_i$表示以$i$为结尾的$\text{AA}$串数量，$b_i$表示以$i$开头的$\text{BB}$串数量，则答案即为$\sum a_ib_{i+1}$。
显然，这个可以通过hash做到$n^2$，并且可以取得$95\%$的好成绩，~~毫无区分意义~~。
然后就是一个非常神仙的思路了：
我们枚举一个长度$len$，然后每隔$len$个字符设立一个关键点。则任何长度$\geq2len$的子串都经过且只经过两个关键点。则我们枚举每一对相邻的关键点，并尝试求出有多少个合法子串经过了它。
我们求出这两个关键点的$\operatorname{LCP}$与$\operatorname{LCS(Longest Common Suffix)}$，这可以直接使用后缀数组+ST表求出。如果它们的和$\geq len$，则显然就有合法的串经过它们，这一数量为$\operatorname{LCP}+\operatorname{LCS}-len+1$个。我们只需要差分就可以得到$a$与$b$数组。
因为$\sum\limits_{i=1}^n\dfrac{n}{i}=n\log n$，所以该算法复杂度即为$O(n\log n)$。
**记得清空所有数组**！！！
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30100;
int T,n,a[N],b[N];
ll res;
char str[N];
struct Suffix_Array{
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],LG[N],mn[N][16],m;
char s[N];
void init(){
for(int i=0;i<N;i++)x[i]=y[i]=buc[i]=sa[i]=ht[i]=rk[i]=LG[i]=0;
memset(mn,0,sizeof(mn));
m='z';
}
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
int RMQ(int l,int r){
if(l>=n||r>=n||l<0||r<0)return 0;
l=rk[l],r=rk[r];
if(l>r)swap(l,r);
l++;
int k=LG[r-l+1];
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
}pre,suf;
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",str),n=strlen(str),memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),res=0;
pre.init(),suf.init();
memcpy(pre.s,str,sizeof(str)),memcpy(suf.s,str,sizeof(str)),reverse(pre.s,pre.s+n);
// printf("%s\n%s\n",pre.s,suf.s);
pre.SA(),suf.SA();
// for(int i=0;i<n;i++)printf("%d ",pre.rk[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",suf.rk[i]);puts("");
for(int len=1;len<=n/2;len++)for(int i=0;i+len<n;i+=len){
int p=i,q=i+len,r=n-q,s=n-p;
int LCP=min(suf.RMQ(p,q),len);
int LCS=min(pre.RMQ(r,s),len-1);
int Delta=LCP+LCS-len+1;
if(Delta>=0)b[p-LCS]++,b[p-LCS+Delta]--,a[q+LCP-Delta]++,a[q+LCP]--;
}
// for(int i=0;i<n;i++)printf("(%d %d)\n",a[i],b[i]);
for(int i=1;i<n;i++)a[i]+=a[i-1],b[i]+=b[i-1];
for(int i=1;i<n;i++)res+=a[i-1]*b[i];
printf("%lld\n",res);
}
return 0;
}
```
# XXII.[[湖南集训]图森](https://www.luogu.com.cn/problem/P3900)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-p3900)
# XXIII.[[NOI2018]你的名字](https://www.luogu.com.cn/problem/P4770)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-p4770)
# XXIV.[CF123D String](https://www.luogu.com.cn/problem/CF123D)
没啥好说的，直接建出笛卡尔树出来，然后统计一下和即可。复杂度$O(n)$，假如你用DC3的话。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100100;
int n,m;
int x[N],y[N],buc[N],sa[N],ht[N],rk[N];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int stk[N],L[N],R[N],tp,lson[N],rson[N],rt;
ll res;
void solve(int x,int las){
res+=1ll*(ht[x]-las)*(R[x]-L[x])*(R[x]-L[x]+1)/2;
if(lson[x])solve(lson[x],ht[x]);
else res+=(n-sa[L[x]])-ht[x];
if(rson[x])solve(rson[x],ht[x]);
else res+=(n-sa[R[x]-1])-ht[x];
}
int main(){
scanf("%s",s),n=strlen(s),m='z';
SA();
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])lson[i]=stk[tp],R[stk[tp]]=i,tp--;
if(tp)rson[stk[tp]]=i;
L[i]=stk[tp],stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
rt=stk[1];
solve(rt,0);
printf("%lld\n",res);
return 0;
}
```
# XXV.[[JSOI2015]串分割](https://www.luogu.com.cn/problem/P6095)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-p6095)
# XXVI.[SP7258 SUBLEX - Lexicographical Substring Search](https://www.luogu.com.cn/problem/SP7258)
在上一题中，我们二分了**后缀**；但这里，我们要二分的是**子串**。
我们设一个$sum_x$表示有多少本质不同子串的字典序小于等于$sa_i$。显然，它是单调增的。则我们可以二分找出$sum_x$小于询问的最右位置，输出即可。
虽然简单，但这是我们接下来很多题的基础。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
typedef long long ll;
int q;
ll sum[N];
namespace Suffix_Array{
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m;
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
int main(){
scanf("%s%d",s,&q),n=strlen(s),m='z';
SA();
sum[0]=n-sa[0];
for(int i=1;i<n;i++)sum[i]=sum[i-1]+(n-sa[i])-ht[i];
// for(int i=0;i<n;i++)printf("%d ",sum[i]);puts("");
for(int x;q--;){
scanf("%d",&x);
int p=lower_bound(sum,sum+n,x)-sum;
for(int i=0;i<x-sum[p-1]+ht[p];i++)putchar(s[sa[p]+i]);putchar('\n');
}
return 0;
}
```
# XXVII.[[BZOJ4310]跳蚤](https://www.lydsy.com/JudgeOnline/problem.php?id=4310)
我们仍然考虑二分子串。设当前二分的子串从位置$pos$开始，长度为$len$。考虑如何编写```check```函数。
一个naive的想法便是从前往后枚举所有极大的**不存在小于二分串的子串**的段，然后将该段数与规定段数作比较。
但是这有点问题——我们发现，这样做每次都是为**段中所有后缀**各添加一个字符，不好快速判断。但我们可以借鉴XIV.[[SDOI2016]生成魔咒](https://www.luogu.com.cn/problem/P4070)的思想，反过来**倒序枚举**极大段，这次每次都只是增加一个前缀了。
于是只要判断该前缀与二分串的字典序关系，如果字典序大于二分串就切一刀即可。
因为所有子串数是$O(n^2)$的，所以实际复杂度为$O(n\log n^2)=O(n\times2\log n)=O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
typedef long long ll;
ll sum[N];
int K;
namespace Suffix_Array{
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m,LG[N],mn[N][20];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
int LCP(int x,int y){
if(x==y)return n-x;
x=rk[x],y=rk[y];
if(x>y)swap(x,y);
x++;
int k=LG[y-x+1];
return min(mn[x][k],mn[y-(1<<k)+1][k]);
}
}
using namespace Suffix_Array;
bool che(ll ip){
int pos=lower_bound(sum,sum+n,ip)-sum,len=ip-sum[pos-1]+ht[pos];
pos=sa[pos];
// printf("%lld:%d,%d\n",ip,pos,len);
int k=0;
for(int i=n-1,j=n-1;i>=0;i=j,k++){//numerate backwards
for(;j>=0;j--){
int tmp=min({LCP(j,pos),i-j+1,len});//the minimum length possible
if(tmp==i-j+1&&tmp<=len)continue;//is ok
if(tmp==len)break;
if(rk[j]>rk[pos])break;//a greater lexicographicity, break.
}
if(i==j)return false;//there's a SINGLE CHARACTER that is lexicographically greater than substring checked, so break out.
}
return k<=K;
}
int main(){
scanf("%d%s",&K,s),n=strlen(s),m='z',SA();
// for(int i=0;i<n;i++)printf("%d ",sa[i]);puts("");
sum[0]=n-sa[0];
for(int i=1;i<n;i++)sum[i]=sum[i-1]+(n-sa[i])-ht[i];
// for(int i=0;i<n;i++)printf("%2d ",i);puts("");
// for(int i=0;i<n;i++)printf("%2d ",s[i]-'a');puts("");
// for(int i=0;i<n;i++)printf("%d ",sum[i]);puts("");
ll l=1,r=sum[n-1];
while(l<r){
ll mid=(l+r)>>1;
if(che(mid))r=mid;
else l=mid+1;
}
int pos=lower_bound(sum,sum+n,l)-sum,len=l-sum[pos-1]+ht[pos];
for(int i=0;i<len;i++)putchar(s[sa[pos]+i]);
return 0;
}
/*
3
ihgjhdgajhdjfjddddfdj
*/
```
# XXVIII.[[BZOJ3277]串](https://www.lydsy.com/JudgeOnline/problem.php?id=3277)/[CF204E Little Elephant and Strings](https://www.luogu.com.cn/problem/CF204E)
这两题是重题，代码改都不改交上去就能A，故放在一起讲。
网上的大多数SA题解都是$O(n\log^2n)$或$O(n\log n)$的复杂度，太令人不爽了。因此，这里有一种复杂度$O(n)$的SA题解。
一看到$O(n)$的SA，就应该猜出我们的目标是什么了——**笛卡尔树**。但是这里我们就要判断笛卡尔树的区间内部出现了多少条不同的原串。在之前的X.[[SCOI2012]喵星球上的点名](https://www.luogu.com.cn/problem/P2336)中，我们使用了$O(n\log n)$的**二维数点**来解决此类问题。但是这题的$K$是固定的，所以有没有更优美的方法呢？
有的！我们可以用two-pointers求出对于每个位置$x$，它左侧最右边的一个位置$lft_x$且使得$[lft_x,x]$中出现了恰好$K$个不同的原串。则我们如果要再来判断区间$[L,R]$是否合法的话，只需要判断是否有$L\leq lft_R$即可。
使用单调栈建笛卡尔树+two-pointers求$lft$+差分计算贡献+DC3后缀排序，即可将复杂度压至$O(n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200100;
int n,m,id[N],A,B,len[N];
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],s[N];
char str[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
int lft[N],occ[N];
int L[N],R[N],lson[N],rson[N],stk[N],tp;
int diff[N];
ll res[N];
void solve(int x,int las){
// printf("%d:[%d,%d]:%d-%d\n",x,L[x],R[x],las,ht[x]);
int tmp;
if(L[x]<=lft[R[x]-1])tmp=ht[x]-las,diff[L[x]]+=tmp,diff[R[x]]-=tmp/*,printf("A:%d:[%d,%d]:%d\n",x,L[x],R[x]-1,tmp)*/;
if(lson[x])solve(lson[x],ht[x]);
else if(B==1)tmp=len[sa[L[x]]]-ht[x],diff[L[x]]+=tmp,diff[L[x]+1]-=tmp/*,printf("B:%d:[%d,%d]:%d\n",x,L[x],L[x],tmp)*/;
if(rson[x])solve(rson[x],ht[x]);
else if(B==1)tmp=len[sa[R[x]-1]]-ht[x],diff[R[x]-1]+=tmp,diff[R[x]]-=tmp/*,printf("C:%d:[%d,%d]:%d\n",x,R[x]-1,R[x]-1,tmp)*/;
}
int main(){
scanf("%d%d",&A,&B);
for(int i=1;i<=A;i++){
scanf("%s",str),m=strlen(str);
for(int j=0;j<m;j++)s[n]=str[j]-'a'+1,id[n]=i,len[n]=m-j,n++;
s[n++]=i+26;
}
// for(int i=0;i<n;i++)printf("%2d ",s[i]);puts("");
m=A+26;
SA();
// for(int i=0;i<n;i++)printf("%2d ",sa[i]);puts("");
// for(int i=0;i<n;i++)printf("%d ",id[sa[i]]);puts("");
// for(int i=0;i<n;i++)printf("%d ",ht[i]);puts("");
for(int i=0,j=0,k=0;j<n;j++){
if(id[sa[j]])k+=!occ[id[sa[j]]]++;
for(;k>=B;i++)if(id[sa[i]])k-=!--occ[id[sa[i]]];
lft[j]=i-1;
}
// for(int i=0;i<n;i++)printf("%d ",lft[i]);puts("");
for(int i=1;i<n;i++){
while(tp&&ht[stk[tp]]>ht[i])lson[i]=stk[tp],R[stk[tp]]=i,tp--;
if(tp)rson[stk[tp]]=i;
L[i]=stk[tp],stk[++tp]=i;
}
while(tp)R[stk[tp--]]=n;
// for(int i=1;i<n;i++)printf("[%d,%d]",L[i],R[i]);puts("");
solve(stk[1],0);
for(int i=1;i<n;i++)diff[i]+=diff[i-1];
// for(int i=0;i<n;i++)printf("%d ",diff[i]);puts("");
for(int i=0;i<n;i++)if(id[sa[i]])res[id[sa[i]]]+=diff[i];
for(int i=1;i<=A;i++)printf("%lld ",res[i]);
return 0;
}
```
# XXIX.[CF700E Cool Slogans](https://www.luogu.com.cn/problem/CF700E)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-cf700e)
# XXX.[[CTSC2012]熟悉的文章](https://www.luogu.com.cn/problem/P4022)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-p4022)
# XXXI.[CF666E Forensic Examination](https://www.luogu.com.cn/problem/CF666E)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-cf666e)
# XXXII.[CF1063F String Journey](https://www.luogu.com.cn/problem/CF1063F)
[题解](https://www.luogu.com.cn/blog/Troverld/solution-cf1063f)
# XXXIII.[CF547E Mike and Friends](https://www.luogu.com.cn/problem/CF547E)
实际上是一道很蠢的问题。
我们直接在后缀数组上二分，求出所有拥有串$s_k$作为前缀的后缀所在的区间，则问题就被转换为某一区间中值在$[l,r]$范围内的数的个数。显然是二维数点问题，于是直接离线后树状数组解决。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=500100;
typedef long long ll;
int A,B,id[N],len[N],pos[N];
namespace Suffix_Array{
int x[N],y[N],buc[N],sa[N],ht[N],rk[N],n,m,mn[N][20],LG[N],s[N];
char str[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<n)^(b+k<n))return false;
if((a+k<n)&&(b+k<n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=0;i<n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[i]]]=i;
for(int k=1;k<n;k<<=1){
int num=0;
for(int i=n-k;i<n;i++)y[num++]=i;
for(int i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=0;i<n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n-1;i>=0;i--)sa[--buc[x[y[i]]]]=y[i];
swap(x,y);
x[sa[0]]=num=0;
for(int i=1;i<n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(num>=n-1)break;
m=num;
}
for(int i=0;i<n;i++)rk[sa[i]]=i;
for(int i=0,k=0;i<n;i++){
if(!rk[i])continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
for(int i=2;i<n;i++)LG[i]=LG[i>>1]+1;
for(int i=1;i<n;i++)mn[i][0]=ht[i];
for(int j=1;j<=LG[n-1];j++)for(int i=1;i+(1<<j)-1<n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
int LCP(int x,int y){
if(x>y)swap(x,y);
x++;
int k=LG[y-x+1];
return min(mn[x][k],mn[y-(1<<k)+1][k]);
}
void Range(int x,int k,int &L,int &R){
int l,r;
x=rk[x];
l=0,r=x;
while(l<r){
int mid=(l+r)>>1;
if(LCP(mid,x)>=k)r=mid;
else l=mid+1;
}
L=r;
l=x,r=n-1;
while(l<r){
int mid=(l+r+1)>>1;
if(LCP(mid,x)>=k)l=mid;
else r=mid-1;
}
R=l;
}
}
using namespace Suffix_Array;
struct Query{
int x,l,r,id;
Query(int _1=0,int _2=0,int _3=0,int _4=0){x=_1,l=_2,r=_3,id=_4;}
friend bool operator <(const Query &x,const Query &y){
return x.x<y.x;
}
}q[N<<1];
int res[N],t[N];
void ADD(int x){while(x<=A)t[x]++,x+=x&-x;}
int SUM(int x){int sum=0;while(x)sum+=t[x],x-=x&-x;return sum;}
int main(){
scanf("%d%d",&A,&B);
for(int i=1;i<=A;i++){
scanf("%s",str),m=strlen(str),len[i]=m,pos[i]=n;
for(int j=0;j<m;j++)s[n]=str[j]-'a'+1,id[n]=i,n++;
s[n++]=i+26;
}
m=A+26;
SA();
for(int i=1,a,b,c,d;i<=B;i++){
scanf("%d%d%d",&c,&d,&a);
Range(pos[a],len[a],a,b);
q[i]=Query(a-1,c,d,-i);
q[i+B]=Query(b,c,d,i);
}
sort(q+1,q+(B<<1)+1);
for(int i=0,j=1;i<n;i++){
if(id[sa[i]])ADD(id[sa[i]]);
while(j<=(B<<1)&&q[j].x<i)j++;
while(j<=(B<<1)&&q[j].x==i){
int tmp=SUM(q[j].r)-SUM(q[j].l-1);
if(q[j].id<0)res[-q[j].id]-=tmp;
else res[q[j].id]+=tmp;
j++;
}
}
for(int i=1;i<=B;i++)printf("%d\n",res[i]);
return 0;
}
```
# XXXIV.[CF653F Paper task](https://www.luogu.com.cn/problem/CF653F)
比较常规的一道题吧。
首先，我们先不考虑“匹配”这一条件，光考虑“不同子串”，就是I.[不同子串个数](https://www.luogu.com.cn/problem/P2408)。
现在我们考虑匹配了，则显然，假设我们现在枚举到位置$i$，则只有区间$[sa_i+ht_i,n]$范围内的端点才是合法的。
怎样判断匹配呢？这里就有一个小技巧了：
我们把`(`看作$+1$，`)`看作$-1$，然后作一个前缀和，记作$s_i$。则子串$[l,r]$合法，当且仅当$s_{l-1}=s_r$，并且$\nexists j\in[l,r],s_j<s_r$。
于是我们就可以用ST表+二分找出这个最远的符合条件的$r$。然后，可以用```vector```存储所有$s_i=k$的位置，最后只要在区间$[sa_i+ht_i,r]$中二分找出所有位置的数量即可。
时间复杂度$O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500100;
int n,m;
namespace Suffix_Array{
int x[N],y[N],buc[N],sa[N],rk[N],ht[N];
char s[N];
bool mat(int a,int b,int k){
if(y[a]!=y[b])return false;
if((a+k<=n)^(b+k<=n))return false;
if((a+k<=n)&&(b+k<=n))return y[a+k]==y[b+k];
return true;
}
void SA(){
for(int i=1;i<=n;i++)buc[x[i]=s[i]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=0;i<=m;i++)buc[i]=0;
for(int i=1;i<=n;i++)buc[x[y[i]]]++;
for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
for(int i=n;i;i--)sa[buc[x[y[i]]]--]=y[i];
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)x[sa[i]]=mat(sa[i],sa[i-1],k)?num:++num;
if(n==num)break;
m=num;
}
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
ht[rk[i]]=k;
}
}
}
using namespace Suffix_Array;
int LG[N],ST[N][20];
int RMQ(int l,int r){
int k=LG[r-l+1];
return min(ST[l][k],ST[r-(1<<k)+1][k]);
}
vector<int>v[N<<1];
ll res;
int main(){
scanf("%d%s",&n,s+1),m=')',SA();
for(int i=1;i<=n;i++)ST[i][0]=(s[i]==')'?ST[i-1][0]-1:ST[i-1][0]+1),v[ST[i][0]+n].push_back(i);
for(int i=2;i<=n;i++)LG[i]=LG[i>>1]+1;
for(int j=1;j<=LG[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
for(int i=1;i<=n;i++){
int l=sa[i]+ht[i]-1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(RMQ(sa[i],mid)>=ST[sa[i]-1][0])l=mid;
else r=mid-1;
}
int pos=ST[sa[i]-1][0]+n;
res+=upper_bound(v[pos].begin(),v[pos].end(),l)-upper_bound(v[pos].begin(),v[pos].end(),sa[i]+ht[i]-1);
}
printf("%lld\n",res);
return 0;
}
```
# XXXV.[树上后缀排序](https://www.luogu.com.cn/problem/P5353)
[My Solution](https://www.luogu.com.cn/blog/Troverld/solution-p5353)