2022.02.20 SA
2022.02.20 SA
如果我还能看见明天黎明，如果我还能再爬起来，我仍会走我的路，哪怕这条路已经荒废许久，也许我们无法拥有感情，我们甚至无法像个正常人一样接受太阳的洗礼，但是我依然会执行我的条约，哪怕不会有人记得我，哪怕我们并不会记入编年史，我们的名字也许会成为辱骂的对象，我依然执行我的信条当其他人都盲目追寻真理的时候，记住，万事皆虚，当其他人的思想都被法律与道德所束缚的时候，记住，万事皆允。 我们躬耕于黑暗却服侍于，并非是我选择了这样的一生，而是一生选了我。——《刺客信条》
SA:
http://www.yhzq-blog.cc/后缀数组算法总结/
段错误：
https://blog.csdn.net/lotluck/article/details/42948593
Step 1 模板代码
1.1 前置知识 基数排序
1.2 代码如下（SA模板1.0）
https://www.luogu.com.cn/problem/P4248
#include
using namespace std;
#define Ri register
const int N=5e5+10;
typedef long long ll;
int n,m,wa[N],wb[N],wv[N],wsi[N],sa[N],ranki[N],r[N];
int height[N],h[N];
int stacki[N],top;
char s[N];
ll ans[N];
inline int cmp(int *r,int a,int b,int len){
return r[a]==r[b]&&r[a+len]==r[b+len];
}
inline void SA(int *r,int *sa,int n,int m){
m=129;
int *x=wa,*y=wb,*t;
for(Ri int i=0;i=j)y[p++]=sa[i]-j;
//这里是按照第一次sa数组的排序，然后记录它前一个的位置，这样就是对suf第二个字符进行排序
//y中存第二个关键词排序后的结果
/*cout<<"sa "< 1.3 重点
1.3.1 关于判断越界
有两种方法：
-
手动判断越界
inline int cmp(int *r,int a,int b,int len){ return r[a]==r[b]&& (a+len>=n?-1:r[a+len])==(b+len>=n?-1:r[b+len]); } -
字符串末尾加0表示结束
r[n++]=0;
Step 2 练习题
P2178 [NOI2015] 品酒大会
https://www.luogu.com.cn/problem/P2178
100pts（别人的）
#include
#include
#include
#include
#define MAXN (300000+100)
using namespace std;
int wt[MAXN],wa[MAXN],wb[MAXN];
int SA[MAXN],Rank[MAXN],Height[MAXN];
char r[MAXN];
int a[MAXN],cnt;
int ID[MAXN],Father[MAXN];
long long Size[MAXN],Max[MAXN],Min[MAXN],Ans[MAXN][2],INF;
int n,m=130;
bool cmp(int *y,int a,int b,int k)
{
int arank1=y[a];
int brank1=y[b];
int arank2=a+k>=n?-1:y[a+k];
int brank2=b+k>=n?-1:y[b+k];
return arank1==brank1 && arank2==brank2;
}
void Build_SA()
{
int *x=wa,*y=wb;
for (int i=0;i=0;--i) SA[--wt[x[i]]]=i;
for (int j=1;j<=n;j<<=1)
{
int p=0;
for (int i=n-j;i=j) y[p++]=SA[i]-j;
for (int i=0;i=0;--i) SA[--wt[x[y[i]]]]=y[i];
m=1;swap(x,y);
x[SA[0]]=0;
for (int i=1;i=n) break;
}
}
void Build_Height()
{
for (int i=0;iHeight[y];
}
int main()
{
memset(&INF,0x7f,sizeof(INF));
scanf("%d",&n);
scanf("%s",r);
for (int i=0;i=0;--i)
{
Ans[i][0]+=Ans[i+1][0];
Ans[i][1]=max(Ans[i][1],Ans[i+1][1]);
}
for (int i=0;i 90pts（我的）
#include
using namespace std;
#define int long long
#define Ri register
const int N=3e6+1000;
const int inf=1e18;
int n,m,a[N];
int r[N],wa[N],wb[N],wv[N],t[N],sa[N],ranki[N];
int height[N];
int fa[N],sizei[N],maxn[N],minn[N],ans[N][2],id[N];
char s[N];
inline int cmp(int *r,int a,int b,int len){
return r[a]==r[b]&&r[a+len]==r[b+len];
}
inline void SA(int *r,int *sa,int n,int m){
m=400;
int *x=wa,*y=wb;
for(Ri int i=0;i=j)y[p++]=sa[i]-j;
for(Ri int i=0;i'9'){
if(ch=='-')w=-1;;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline int cmp1(int x,int y){
return height[x]>height[y];
}
signed main(){
//freopen("P2178_3.in","r",stdin);
//freopen("P2178.out","w",stdout);
n=read();
//cout<-1)merge(id[i],id[i]-1);
//cout<<"Case 5"<=0;i--)ans[i][0]+=ans[i+1][0],ans[i][1]=max(ans[i][1],ans[i+1][1]);
for(Ri int i=0;i P4051 [JSOI2007]字符加密
https://www.luogu.com.cn/problem/P4051
100pts（标准求SA模板2.0）
#include
using namespace std;
#define Ri register
const int N=2e5+10;
int n,m,r[N],sa[N],wa[N],wb[N],wv[N],wt[N],ranki[N],height[N];
char s[N];
inline int cmp(int *r,int a,int b,int len){
return r[a]==r[b]&&r[a+len]==r[b+len];
}
inline void SA(int *r,int *sa,int n,int m){
m=400;
int *x=wa,*y=wb,*t,p=1;
for(Ri int i=0;i=j)y[p++]=sa[i]-j;
for(Ri int i=0;i=n)break;
}
//for(Ri int i=0;i SP694 DISUBSTR - Distinct Substrings
https://www.luogu.com.cn/problem/SP694
100pts（SA模板3.0）
#include
using namespace std;
#define Ri register
#define ll long long
const int N=5e4+10;
int T,n,m,r[N],sa[N],wa[N],wb[N],wv[N],wt[N],ranki[N],height[N];
char s[N];
inline int cmp(int *r,int a,int b,int len){
return r[a]==r[b]&&(a+len>=n?-1:r[a+len])==(b+len>=n?-1:r[b+len]);
//更改处1：增加比较超过n的地方
}
inline void SA(int *r,int *sa,int n,int m){
int p=1,*x=wa,*y=wb,*t;
m=1010;
for(Ri int i=0;i=0;i--)sa[--wt[x[i]]]=i;
for(Ri int j=1;j<=n;j<<=1){
p=0;
for(Ri int i=n-j;i=j)y[p++]=sa[i]-j;
for(Ri int i=0;i=0;i--)sa[--wt[wv[i]]]=y[i];
p=1;
t=x;x=y;y=t;
x[sa[0]]=0;
for(Ri int i=1;i=n)break;
}
}
inline void calc(int *r,int *sa,int n){
int k=0,j;
for(Ri int i=0;i>T;
while(T--){
scanf("%s",s);
n=strlen(s);
for(Ri int i=0;i P2852 [USACO06DEC]Milk Patterns G(重复的K次最长字串：RMQ+SA)
https://www.luogu.com.cn/problem/P2852
100pts：
#include
#include
#include
#include
#include
using namespace std;
#define Ri register
const int N=2e4+10;
const int inf=0x3f3f3f3f;
int n,m,K;
int r[N],sa[N],ranki[N],height[N],wa[N],wb[N],wv[N],wt[N];
int a[N],f[N][20],logi[N];
inline int cmp(int *r,int a,int b,int len){
return r[a]==r[b]&&(a+len>=n?-1:r[a+len])==(b+len>=n?-1:r[b+len]);
}
inline void SA(int *r,int *sa,int n,int m){
m=500;
int *x=wa,*y=wb,*t,p=1;
for(Ri int i=0;i=0;i--)sa[--wt[x[i]]]=i;
for(Ri int j=1;j<=n;j*=2,m=p){
p=0;
for(Ri int i=n-j;i=j)y[p++]=sa[i]-j;
for(Ri int i=0;i=0;i--)sa[--wt[wv[i]]]=y[i];
p=1;
t=x;x=y;y=t;
x[sa[0]]=0;
for(Ri int i=1;i=n)break;
}
}
inline void calc(int *r,int *sa,int n){
int k=0,j=1;
for(Ri int i=0;i=K;
}
inline int erfen(int l,int r){
int L=l,R=r+1,mid,ans;
while(L<=R){
mid=(L+R)>>1;
cout<<"L "<'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline int query(int l,int r){
int k=logi[r-l];
return min(f[l][k],f[r-(1<