参考:2020年牛客多校A题
将字符串化为B数组之后,会发现,它其实是由两部分组成的。例如aaaabaaab
的B数组为011102114,那么我们可以将B拆成两半,前面一部分是01110,后面一部分是2114。我们会发现,所有长度的B数组前面部分的格式都是一样的,而后面一部分都是\(B(t_1..t_n)\)的子串。
所以我们可以先对前面一部分对长度进行排序,再用后缀数组对后面那部分进行排序。
但是我们会发现,前面这部分排序的过程中,0111和0110的长度是一样的,要把他区别开来,所以就让0111的长度变为4.5,这样既满足了比0110大,又满足了比01110小。
// Created by CAD on 2020/7/14.
#include <bits/stdc++.h>
#define fi first
#define se second
#define pfii pair<pair<float,int>,int>
using namespace std;
vector<pfii> v;
const int maxn=1e5+5;
int cnt[maxn];
void radix(int *str,int *a,int *b,int n,int m){
for(int i=0;i<=m;++i) cnt[i]=0;
for(int i=0;i<n;++i) ++cnt[str[a[i]]];
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;--i) b[--cnt[str[a[i]]]]=a[i];
}
int rk[maxn],a[maxn],b[maxn];
void suffix_array(int *str,int *sa,int n,int m){
for(int i=0;i<n;++i) rk[i]=i;
radix(str,rk,sa,n,m);
rk[sa[0]]=0;
for(int i=1;i<n;++i) rk[sa[i]]=rk[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for(int i=0;1<<i <n;++i){
for(int j=0;j<n;++j){
a[j]=rk[j]+1;
b[j]=j+(1<<i)>=n?0:rk[j+(1<<i)]+1;
sa[j]=j;
}
radix(b,sa,rk,n,n);
radix(a,rk,sa,n,n);
rk[sa[0]]=0;
for(int j=1;j<n;++j)
rk[sa[j]]=rk[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);
}
}
int t[maxn],sa[maxn];
int main() {
int n;
while(cin>>n){
string s;cin>>s;
v.clear();
int aa=0,bb=0;
for(int i=0;i<n;++i){
while(aa<n-1&&(aa < i || s[aa] != 'a')) aa++;
while(bb<n-1&&(bb < i || s[bb] != 'b')) bb++;
v.push_back({{abs(bb - aa) + 1+((s[aa]!='a'||s[bb]!='b')?0.5:0), n - i - (abs(bb - aa) + 1)}, i+1});
}
aa=-1, bb=-1;
int m=0;
for(int i=0;i<n;++i)
if(s[i]=='a') t[i]=(~aa ? (i - aa) : 0), aa=i,m=max(m,t[i]);
else t[i]=(~bb ? (i - bb) : 0), bb=i,m=max(m,t[i]);
suffix_array(t,sa,n,m);
rk[n]=-1;
for(auto &i:v)
i.fi.se=rk[n-i.fi.se]+1;
sort(v.begin(),v.end());
for(auto i:v)
cout<<i.se<<" ";
cout<<endl;
}
return 0;
}
原文链接: https://www.cnblogs.com/cader/p/13303700.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/366641
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!