技术教程 2022.02.21 SA 正文

2022.02.21 SA

2022-10-17,

2022.02.21 SA

当我年少轻狂时，我曾拥有自由，但我并不明白它的意义。我曾拥有时间，但我没有意识到它的珍贵。我曾拥有爱，但我从未用心去体会。数十年的时间考验后，我终于理解了三者的真谛。　我已风烛残年，这种理解已经逐渐变成一种满足。爱，自由和时间，曾一度被我挥霍，而今成为了我前进的动力。而我将最特别的爱，献给最亲爱的你和我们的孩子们，以及刺客联盟的兄弟姐妹们，并献给赋予我们生命的那壮美奇妙，让人产生无限遐想的世界。此爱永恒，Mia Sofia。永远都属于你的--艾吉奥·奥迪托雷。——刺客信条：余烬

P6095 [JSOI2015]串分割

100pts

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<bits/stdc++.h>

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<n)^(b+k<n))return 0;

	if(a+k<n&&b+k<n)return y[a+k]==y[b+k];*/

	return 0;

}

inline void SA(int *r,int *sa,int n,int m){

	int p=1,*x=wa,*y=wb,*t;

	m=400;

	for(Ri int i=0;i<m;i++)wt[i]=0;

	for(Ri int i=0;i<n;i++)++wt[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

	for(Ri int i=n-1;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<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		//cout<<"y "<<endl;

		//for(Ri int i=0;i<p;i++)cout<<y[i]<<" ";cout<<endl;

		for(Ri int i=0;i<m;i++)wt[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++wt[wv[i]];

		for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

		/*cout<<"wv "<<endl;

		for(Ri int i=0;i<n;i++)cout<<wv[i]<<" ";cout<<endl;

		cout<<"wt "<<endl;

		for(Ri int i=0;i<n;i++)cout<<wt[i]<<" ";cout<<endl;*/

		for(Ri int i=n-1;i>=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;i<n;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p:++p;

		/*cout<<"sa "<<endl;

		for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;

		cout<<"ranki "<<endl;

		for(Ri int i=0;i<n;i++)cout<<x[i]<<" ";cout<<endl;*/

		m=p+1;

		if(p>n-2)break;

	}

	for(Ri int i=0;i<n;i++)ranki[sa[i]]=i;

	/*cout<<"sa "<<endl;

	for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;

	cout<<"ranki "<<endl;

	for(Ri int i=0;i<n;i++)cout<<ranki[i]<<" ";cout<<endl;*/

}

inline bool check(int id){

	for(Ri int i=0;i<len;i++){

		int now=i;

		for(Ri int j=0;j<tot;j++){

			now+=len-(ranki[now]>id);

			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<n;i++)s[i+n]=s[i];

	n<<=1;

	for(Ri int i=0;i<n;i++)r[i]=s[i];//,cout<<s[i];cout<<endl;

	SA(r,sa,n,m);

	int L=0,R=n-1,mid;

	n>>=1;

	while(L<R){

		mid=(L+R)>>1;

		//cout<<"L "<<L<<" R "<<R<<" mid "<<mid<<endl;

		if(check(mid))R=mid;

		else L=mid+1;

	}

	//cout<<R<<endl;

	for(Ri int i=0;i<(n<<1);i++)if(ranki[i]==R)

	for(Ri int j=0;j<len;j++)cout<<s[j+i];

	return 0;

}

/*

4 2

4321

ans 32

*/

P3181 [HAOI2016]找相同字符（万事皆允：eleveni修订版SA4.0）

https://www.luogu.com.cn/problem/P3181

\(O(n^2)\) 复杂度、40pts

新版思路：比较不能用-1，那就全部向右平移，只要把m开得够大就行。

#include<bits/stdc++.h>

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<n?r[a+k]:-1)==(b+k<n?r[b+k]:-1);

	//return r[a]==r[b]&&r[a+k]==r[b+k];

}

inline void SA(int *r,int *sa,int n,int m){

	int *x=wa,*y=wb,*t;

	int p=1;

	m=400;

	for(Ri int i=0;i<m;i++)wt[i]=0;

	for(Ri int i=0;i<n;i++)++wt[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

	for(Ri int i=n-1;i>=0;i--)sa[--wt[x[i]]]=i;

	for(Ri int j=1;j<n;j<<=1,m=p){

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		for(Ri int i=0;i<m;i++)wt[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++wt[wv[i]];

		for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

		for(Ri int i=n-1;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;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

		m=p;

		if(p>=n)break;

	}

	/*cout<<"sa "<<endl;

	for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;*/

}

inline void calc(int *r,int *sa,int n){

	int k=0,j;

	for(Ri int i=0;i<n;i++)ranki[sa[i]]=i;

	height[0]=0;

	for(Ri int i=0;i<n;i++){

		if(ranki[i]==0)continue;

		if(k)--k;

		j=sa[ranki[i]-1];

		while(i+k<n&&j+k<n&&r[i+k]==r[j+k])++k;

		height[ranki[i]]=k;

	}

	/*cout<<"ranki "<<endl;

	for(Ri int i=0;i<n;i++)cout<<ranki[i]<<" ";cout<<endl;

	cout<<"height "<<endl;

	for(Ri int i=0;i<n;i++)cout<<height[i]<<" ";cout<<endl;*/

}

inline int query(int l,int r){

	if(l>r)swap(l,r);++l;

	int k=logi[r-l+1];

	return min(f[l][k],f[r-(1<<k)+1][k]);

}

signed main(){

	memset(f,inf,sizeof(f));

	scanf("%s%s",s,t);

	lens=strlen(s);lent=strlen(t);

	for(Ri int i=0;i<lens;i++)r[i]=s[i]+5;

	r[lens]=4;

	for(Ri int i=0;i<lent;i++)r[i+lens+1]=t[i]+5;

	n=lens+lent+1;

	r[n++]=0;

	/*cout<<"r "<<endl;

	for(Ri int i=0;i<n;i++)cout<<r[i]<<" ";cout<<endl;*/

	SA(r,sa,n,m);calc(r,sa,n);

	logi[0]=logi[1]=0;logi[2]=1;

	for(Ri int i=3;i<=n;i++)logi[i]=logi[i/2]+1;

	/*cout<<"logi "<<endl;

	for(Ri int i=0;i<n;i++)cout<<logi[i]<<" ";cout<<endl;*/

	for(Ri int i=1;i<n;i++)f[i][0]=height[i];

	/*cout<<"before r "<<endl;

	for(Ri int i=0;i<n;i++)cout<<(char)r[i];cout<<endl;

	//--n;

	cout<<"after r "<<endl;

	for(Ri int i=0;i<n;i++)cout<<(char)r[i];cout<<endl;*/

	for(Ri int i=1;i<=18;i++)

	for(Ri int j=1;j+(1<<i)-1<n;j++)

	f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);

	/*cout<<"f "<<endl;

	for(Ri int i=1;i<n;i++){

		for(Ri int j=0;j<=10;j++)cout<<f[i][j]<<" ";

		cout<<endl;

	}*/

	int ans=0;

	for(Ri int i=0;i<lens;i++){

		for(Ri int j=lens+1;j<n;j++){

			int lcp=query(ranki[i],ranki[j]);

			//cout<<"L "<<ranki[i]<<" R "<<ranki[j]<<" lcp "<<lcp<<endl;

			ans+=lcp;

		}

	}

	cout<<ans;

	return 0;

}

\(O(nlogn)\) 复杂度、别人的好看的代码、100pts

我的代码丑得难以直视……心塞……

来自

https://www.luogu.com.cn/blog/boshi/solution-p3181

#include <iostream>

#include <cstring>

#include <cstdio>

#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;w<n;w<<=1)

        {

            int p=0;

            for(int i=n-w+1;i<=n;i++)yp[++p]=i;

            for(int i=1;i<=n;i++)if(SA[i]>w)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];

pair<int,ll>stk[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<bits/stdc++.h>

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<n?r[a+k]:-1)==(b+k<n?r[b+k]:-1);

	//return r[a]==r[b]&&r[a+k]==r[b+k];

}

inline void SA(int *r,int *sa,int n,int m){

	int *x=wa,*y=wb,*t;

	int p=1;

	m=400;

	for(Ri int i=0;i<m;i++)wt[i]=0;

	for(Ri int i=0;i<n;i++)++wt[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

	for(Ri int i=n-1;i>=0;i--)sa[--wt[x[i]]]=i;

	for(Ri int j=1;j<n;j<<=1,m=p){

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		for(Ri int i=0;i<m;i++)wt[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++wt[wv[i]];

		for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

		for(Ri int i=n-1;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;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

		m=p;

		if(p>=n)break;

	}

	/*cout<<"sa "<<endl;

	for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;*/

}

inline void calc(int *r,int *sa,int n){

	int k=0,j;

	for(Ri int i=0;i<n;i++)ranki[sa[i]]=i;

	height[0]=0;

	for(Ri int i=0;i<n;i++){

		if(ranki[i]==0)continue;

		if(k)--k;

		j=sa[ranki[i]-1];

		while(i+k<n&&j+k<n&&r[i+k]==r[j+k])++k;

		height[ranki[i]]=k;

	}

	/*cout<<"ranki "<<endl;

	for(Ri int i=0;i<n;i++)cout<<ranki[i]<<" ";cout<<endl;

	cout<<"height "<<endl;

	for(Ri int i=0;i<n;i++)cout<<height[i]<<" ";cout<<endl;*/

}

inline bool check(int minn){

	int vis[110];

	memset(vis,0,sizeof(vis));

	for(Ri int i=2;i<n;i++){

		if(height[i]<minn){

			int flag=0;

			for(Ri int j=1;j<=T;j++)flag+=vis[j];

			if(flag==T)return true;

			memset(vis,0,sizeof(vis));

		}else{

			if(height[i-1]<minn)vis[color[i-1]]=1;

			vis[color[i]]=1;

		}

	}

	return false;

}

signed main(){

	cin>>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<n;i++)cout<<s[i];cout<<endl;

	//for(Ri int i=0;i<n;i++)cout<<color[i]<<" ";cout<<endl;

	n=0;

	for(Ri int i=0;i<(int)strlen(s);i++){

		r[n++]=s[i]+5;

		if(color[i]+1==color[i+1])r[n++]=4;

	}

	r[n++]=0;

	//for(Ri int i=0;i<n;i++)cout<<i<<" "<<(char)r[i]<<endl;

	memset(color,0,sizeof(color));

	SA(r,sa,n,m);calc(r,sa,n);

	for(Ri int i=0,j=1;i<n-1;i++){

		if(r[i]==4)++j;

		color[ranki[i]]=j;

	}

	/*cout<<"color "<<endl;

	for(Ri int i=0;i<=n;i++)cout<<color[i]<<" ";cout<<endl;

	cout<<check(1)<<" "<<check(2)<<" "<<check(3)<<endl;*/

	int L=0,R=maxn+1,mid=0,ans=0;

	while(L<R){

		mid=(L+R)/2;

		//cout<<"L "<<L<<" R "<<R<<" mid "<<mid<<endl;

		if(check(mid))L=mid,ans=mid;

		else R=mid-1;

		//cout<<mid<<endl;

	}

	cout<<ans;

	return 0;

}

/*

3

abcb

bca

acbc

*/

100pts

#include<bits/stdc++.h>

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<n?r[a+k]:-1)==(b+k<n?r[b+k]:-1);

	//return r[a]==r[b]&&r[a+k]==r[b+k];

}

inline void SA(int *r,int *sa,int n,int m){

	int *x=wa,*y=wb,*t;

	int p=1;

	m=400;

	for(Ri int i=0;i<m;i++)wt[i]=0;

	for(Ri int i=0;i<n;i++)++wt[x[i]=r[i]];

	for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

	for(Ri int i=n-1;i>=0;i--)sa[--wt[x[i]]]=i;

	for(Ri int j=1;j<n;j<<=1,m=p){

		p=0;

		for(Ri int i=n-j;i<n;i++)y[p++]=i;

		for(Ri int i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;

		for(Ri int i=0;i<m;i++)wt[i]=0;

		for(Ri int i=0;i<n;i++)wv[i]=x[y[i]];

		for(Ri int i=0;i<n;i++)++wt[wv[i]];

		for(Ri int i=1;i<m;i++)wt[i]+=wt[i-1];

		for(Ri int i=n-1;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;i++)

		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

		m=p;

		if(p>=n)break;

	}

	/*cout<<"sa "<<endl;

	for(Ri int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;*/

}

inline void calc(int *r,int *sa,int n){

	int k=0,j;

	for(Ri int i=0;i<n;i++)ranki[sa[i]]=i;

	height[0]=0;

	for(Ri int i=0;i<n;i++){

		if(ranki[i]==0)continue;

		if(k)--k;

		j=sa[ranki[i]-1];

		while(i+k<n&&j+k<n&&r[i+k]==r[j+k])++k;

		height[ranki[i]]=k;

	}

	/*cout<<"ranki "<<endl;

	for(Ri int i=0;i<n;i++)cout<<ranki[i]<<" ";cout<<endl;

	cout<<"height "<<endl;

	for(Ri int i=0;i<n;i++)cout<<height[i]<<" ";cout<<endl;*/

}/*

inline bool check(int minn){

	int vis[110];

	memset(vis,0,sizeof(vis));

	for(Ri int i=2;i<n;i++){

		if(height[i]<minn){

			int flag=0;

			for(Ri int j=1;j<=T;j++)flag+=vis[j];

			if(flag==T)return true;

			memset(vis,0,sizeof(vis));

		}else{

			if(height[i-1]<minn)vis[color[i-1]]=1;

			vis[color[i]]=1;

		}

	}

	return false;

}*/

inline bool check(int mid){

	int vis[10];

	memset(vis,0,sizeof(vis));

	for(Ri int i=2;i<n;i++){

		if(height[i]>=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<n;i++)cout<<s[i];cout<<endl;

	//for(Ri int i=0;i<n;i++)cout<<color[i]<<" ";cout<<endl;

	/*n=0;

	for(Ri int i=0,j=0;i<(int)strlen(s);i++){

		r[n++]=s[i]+5;

		if(color[i]+1==color[i+1])r[n++]=temp[j++];

	}*/

	r[n++]=0;

	for(Ri int i=0;i<n;i++)r[i]=s[i];//,cout<<(char)r[i];cout<<endl;

	//for(Ri int i=0;i<n;i++)cout<<i<<" "<<(char)r[i]<<endl;

	//memset(color,0,sizeof(color));

	SA(r,sa,n,m);calc(r,sa,n);

	/*for(Ri int i=0,j=1;i<n-1;i++){

		if(r[i]==(int)temp[j-1])++j;

		color[ranki[i]]=j;

	}

	cout<<"color "<<endl;

	for(Ri int i=0;i<=n;i++)cout<<color[i]<<" ";cout<<endl;*/

	//cout<<check(1)<<" "<<check(2)<<" "<<check(3)<<endl;

	int L=0,R=n,mid=0,ans=0;

	while(L+1<R){

		mid=(L+R)/2;

		//cout<<"L "<<L<<" R "<<R<<" mid "<<mid<<endl;

		if(check(mid))L=mid;

		else R=mid;

		//cout<<mid<<endl;

	}

	if(check(R))ans=R;

	else ans=L;

	cout<<ans;

	return 0;

}

/*

3

abcb

bca

acbc

*/

2022.02.21 SA的相关教程结束。

《2022.02.21 SA.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!