2022.02.21 SA
2022.02.21 SA
当我年少轻狂时，我曾拥有自由，但我并不明白它的意义。我曾拥有时间，但我没有意识到它的珍贵。我曾拥有爱，但我从未用心去体会。数十年的时间考验后，我终于理解了三者的真谛。 我已风烛残年，这种理解已经逐渐变成一种满足。爱，自由和时间，曾一度被我挥霍，而今成为了我前进的动力。而我将最特别的爱，献给最亲爱的你和我们的孩子们，以及刺客联盟的兄弟姐妹们，并献给赋予我们生命的那壮美奇妙，让人产生无限遐想的世界。此爱永恒，Mia Sofia。永远都属于你的--艾吉奥·奥迪托雷。——刺客信条：余烬
P6095 [JSOI2015]串分割
100pts
#include
#include
#include
#include
#include
using namespace std;
#define Ri register
const int N=4e5+10;
int n,m,tot,len;
int r[N],sa[N],ranki[N],height[N],wa[N],wb[N],wv[N],wt[N];
char s[N];
inline int cmp(int *y,int a,int b,int k){
return y[a]==y[b]&&(a+k>=n?-1:y[a+k])==(b+k>=n?-1:y[b+k]);
/*if(y[a]!=y[b])return 0;
if((a+k=0;i--)sa[--wt[x[i]]]=i;
for(Ri int j=1;j=j)y[p++]=sa[i]-j;
//cout<<"y "<=0;i--)sa[--wt[wv[i]]]=y[i];
p=0;
t=x;x=y;y=t;
x[sa[0]]=0;
for(Ri int i=1;in-2)break;
}
for(Ri int i=0;iid);
if(now-i>=n)return true;
}
}
return false;
}
signed main(){
cin>>n>>tot;scanf("%s",s);
len=n/tot+(n%tot!=0);
for(Ri int i=0;i>=1;
while(L>1;
//cout<<"L "< P3181 [HAOI2016]找相同字符（万事皆允：eleveni修订版SA4.0）
https://www.luogu.com.cn/problem/P3181
\(O(n^2)\) 复杂度、40pts
新版思路：比较不能用-1，那就全部向右平移，只要把m开得够大就行。
#include
using namespace std;
#define Ri register
const int N=4e5+10;
const int inf=0x3f3f3f3f;
int n,m,r[N],sa[N],ranki[N],height[N],wa[N],wb[N],wv[N],wt[N];
int f[N][20],lens,lent,logi[N];
char s[N],t[N];
inline int cmp(int *r,int a,int b,int k){
return r[a]==r[b]&&(a+k=0;i--)sa[--wt[x[i]]]=i;
for(Ri int j=1;j=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;
}
/*cout<<"sa "<r)swap(l,r);++l;
int k=logi[r-l+1];
return min(f[l][k],f[r-(1< \(O(nlogn)\) 复杂度、别人的好看的代码、100pts
我的代码丑得难以直视……心塞……
来自
https://www.luogu.com.cn/blog/boshi/solution-p3181
#include
#include
#include
#define MX 823123
using namespace std;
typedef long long ll;
typedef struct tSA
{
int str[MX],n,m;
int rank[MX],SA[MX],het[MX];
int buk[MX],yp[MX];
bool cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
void jsort()
{
for(int i=0;i<=m;i++)buk[i]=0;
for(int i=1;i<=n;i++)buk[rank[yp[i]]]++;
for(int i=1;i<=m;i++)buk[i]+=buk[i-1];
for(int i=n;i>=1;i--)SA[buk[rank[yp[i]]]--]=yp[i];
}
void getSA()
{
for(int i=1;i<=n;i++)rank[i]=str[i],yp[i]=i;
m=28;jsort();
for(int w=1;ww)yp[++p]=SA[i]-w;
jsort(),swap(rank,yp),rank[SA[1]]=p=1;
for(int i=2;i<=n;i++)rank[SA[i]]=(cmp(yp,SA[i],SA[i-1],w)?p:++p);
m=p;
}
int k=0;
for(int i=1;i<=n;i++)
{
k=(k?k-1:0);
while(str[i+k]==str[SA[rank[i]-1]+k])k++;
het[rank[i]]=k;
}
}
}SA;
SA sa;
char str[MX];
int l1,l2,top,sum[MX];
pairstk[MX];
void work()
{
ll ans=0;
stk[0]=make_pair(1,0);
for(int i=1;i<=sa.n;i++)sum[i]=sum[i-1]+(sa.SA[i]<=l1);
for(int i=1;i<=sa.n;i++)
{
while(top&&sa.het[stk[top].first]>sa.het[i])top--;
top++;
stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*sa.het[i]+stk[top-1].second);
if(sa.SA[i]>l1+1)ans+=stk[top].second;
}
top=0;
for(int i=1;i<=sa.n;i++)sum[i]=sum[i-1]+(sa.SA[i]>l1+1);
for(int i=1;i<=sa.n;i++)
{
while(top&&sa.het[stk[top].first]>sa.het[i])top--;
top++;
stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*sa.het[i]+stk[top-1].second);
if(sa.SA[i]<=l1)ans+=stk[top].second;
}
printf("%lld\n",ans);
}
int main()
{
scanf("%s",str+1);l1=strlen(str+1);
scanf("%s",str+l1+2);
str[l1+1]='z'+1;
sa.n=strlen(str+1);
for(int i=1;i<=sa.n;i++)sa.str[i]=str[i]-'a'+1;
sa.getSA();
work();
return 0;
}
P5546 [POI2000]公共串（出ub【未定义行为】了）
https://www.luogu.com.cn/problem/P5546
28pts
这次ub是因为没有把数组初始化。
#include
using namespace std;
#define int long long
#define Ri register
const int N=1e5+100;
int T,n,m,r[N],sa[N],ranki[N],height[N],wa[N],wb[N],wv[N],wt[N];
int color[N];
char s[N];
inline int cmp(int *r,int a,int b,int k){
return r[a]==r[b]&&(a+k=0;i--)sa[--wt[x[i]]]=i;
for(Ri int j=1;j=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;
}
/*cout<<"sa "<>T;
int maxn=0;
for(Ri int i=1;i<=T;i++){
scanf("%s",s+n);
for(Ri int j=n;j<(int)strlen(s);j++)color[j]=i;
maxn=max(maxn,(int)strlen(s)-n);
n=strlen(s);
}
//for(Ri int i=0;i 100pts
#include
using namespace std;
#define int long long
#define Ri register
const int N=1e5+100;
int T,n,m,r[N],sa[N],ranki[N],height[N],wa[N],wb[N],wv[N],wt[N];
int color[N];
char s[N],t[10][2010];
char temp[10] = {'!', '@', '#', '$', 0};
inline int cmp(int *r,int a,int b,int k){
return r[a]==r[b]&&(a+k=0;i--)sa[--wt[x[i]]]=i;
for(Ri int j=1;j=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;
}
/*cout<<"sa "<=mid)vis[color[sa[i]]]=1;
else{
int flag=0;
for(Ri int j=1;j<=T;j++){
if(!vis[j])flag=1;
vis[j]=0;
}
if(!flag)return true;
vis[color[sa[i]]]=1;
}
}
int flag=0;
for(Ri int i=1;i<=T;i++){
if(!vis[i])flag=1;
vis[i]=0;
}
if(!flag)return true;
else return false;
}
signed main(){
cin>>T;
int maxn=0;
n=0;
for(Ri int i=1;i<=T;i++){
scanf("%s",t[i]);
maxn=max(maxn,(int)strlen(t[i]));
for(Ri int j=0;j<(int)strlen(t[i]);j++)color[n]=i,s[n++]=t[i][j];
if(i!=T)s[n++]=i;
}
//for(Ri int i=0;i