题目链接
题意分析
给你一个字符串 让你求\(1-n\)长度下的字符串的中字典序最小并且最靠左的字符串的开头位置
我们考虑先建出\(SA\)
然后考虑对于一个字符串后缀排序之后
baba
后缀排序之后 先不管位置 只关心字典序
数字代表当前更新长度
a 1
aba 2 3
ba
baba 4
我们可以发现 第二个后缀还可以更新长度为\(1\)的子串
所以我们考虑使用二分 求刚好可以满足的位置
然后我们再使用\(RMQ\)求这些位置中对应原串位置最靠左的位置
然后更新即可
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 608611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
char s[M];
int n,key,have;int num[M],res[M],ans[M];
int ST[M][20][2],lg[M];
int SA[M],rnk[M],cdy[M],wzy[M],vis[M],hei[M];
IL void Rsort()
{
for(R int i=0;i<=key;++i) vis[i]=0;
for(R int i=1;i<=n;++i) vis[cdy[i]]++;
for(R int i=1;i<=key;++i) vis[i]+=vis[i-1];
for(R int i=n;i;--i) SA[vis[cdy[wzy[i]]]--]=wzy[i];
}
IL void get_SA()
{
for(R int i=1;i<=n;++i) cdy[i]=num[i],wzy[i]=i;Rsort();
for(R int x=1;x<=n;x<<=1)
{
int cnt=0;
for(R int i=n-x+1;i<=n;++i) wzy[++cnt]=i;
for(R int i=1;i<=n;++i) if(SA[i]>x) wzy[++cnt]=SA[i]-x;
Rsort();swap(cdy,wzy);cdy[SA[cnt=1]]=1;
for(R int i=2;i<=n;++i)
cdy[SA[i]]=(wzy[SA[i]]==wzy[SA[i-1]]&&wzy[SA[i]+x]==wzy[SA[i-1]+x] ? cnt:++cnt);
if(cnt==n) break;
else key=cnt;
}
}
IL void get_hei()
{
for(R int i=1;i<=n;++i) rnk[SA[i]]=i;
int lat,k=0;
for(R int i=1;i<=n;++i)
{
if(k) --k;
lat=SA[rnk[i]-1];
while(num[lat+k]==num[i+k]) ++k;
hei[rnk[i]]=k;
}
}
IL void pre()
{
for(R int i=1;(1<<i)<=300000;++i) lg[1<<i]=i;
for(R int i=2;i<=300000;++i) if(!lg[i]) lg[i]=lg[i-1];
for(R int i=1;i<=n;++i) ST[i][0][0]=hei[i];
for(R int j=1;(1<<j)<=n;++j)
for(R int i=1;i<=n;++i)
ST[i][j][0]=min(ST[i][j-1][0],ST[i+(1<<(j-1))][j-1][0]);
for(R int i=1;i<=n;++i) ST[i][0][1]=SA[i];
for(R int j=1;(1<<j)<=n;++j)
for(R int i=1;i<=n;++i)
ST[i][j][1]=min(ST[i][j-1][1],ST[i+(1<<(j-1))][j-1][1]);
}
IL int qury_hei(int le,int ri)
{
if(le>ri) swap(le,ri);++le;int lx=lg[ri-le+1];
return min(ST[le][lx][0],ST[ri-(1<<lx)+1][lx][0]);
}
IL int qury_min(int le,int ri)
{
if(le>ri) swap(le,ri);int lx=lg[ri-le+1];
return min(ST[le][lx][1],ST[ri-(1<<lx)+1][lx][1]);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(have);read(n);
if(have==26)
{
scanf("%s",s+1);key=130;
for(R int i=1;i<=n;++i) num[i]=s[i]-'0'+1;
}
else
{
for(R int i=1;i<=n;++i) read(num[i]),res[i]=num[i];
sort(res+1,res+n+1);key=unique(res+1,res+n+1)-res-1;
for(R int i=1;i<=n;++i) num[i]=lower_bound(res+1,res+key+1,num[i])-res;
// for(R int i=1;i<=n;++i)
// printf("%d%c",num[i],(i==n ? '\n':' '));
// printf("key %d\n",key);
}
get_SA();get_hei();pre();
// printf("SA : ");for(R int i=1;i<=n;++i) printf("%d%c",SA[i],(i==n ? '\n':' '));
// printf("height : ");for(R int i=1;i<=n;++i) printf("%d%c",hei[i],(i==n ? '\n':' '));
for(R int i=1,tail=1;i<=n;++i)
{
while(tail<n&&n-SA[tail]+1<i) ++tail;
//维护单调指针
ans[i]=SA[tail];
int le=tail+1,ri=n,can=-1;
while(le<=ri)
{
int mid=(le+ri)>>1;
if(qury_hei(tail,mid)>=i) can=mid,le=mid+1;
else ri=mid-1;
}
//二分那个位置 用lcp判断是否可以满足贡献出那个串
if(can!=-1) ans[i]=min(ans[i],qury_min(tail,can));
//存在的话 我们就用中间最左端的位置更新
}
for(R int i=1;i<=n;++i) printf("%d%c",ans[i],(i==n ? '\n':' '));
// fclose(stdin);
// fclose(stdout);
return 0;
}