SAにおける基数ソートのサボり方について

1514 ワード
アルゴリズム その他
標準的なSAの書き方を習ったことがないので、以前は自分の盲yyのn*log^2に従って書いていました
何度も引っかかった
rk[]とrk 2[]を第1および第2のキーワードとしてsort//として記録すると、第1のキーワード秩序基数ソート定数が大きくなります
luoguテンプレートn*log^2 70分
基数(巨大定数版)ソート9 sACに変更
そこで自分yyは複雑さを知らないアルゴリズムを出した.複雑度はn*log*log(n/log)くらい
実測5 s AC
アルゴリズムの記録sa[i]は順位のiの位置を表します
まずsaをrk順に並べて普通のベース列と何の違いもありません
次に考えてみましょう
毎回rk[sa[i]]は秩序化され,rk 2[sa[i]]は無秩序である.
そこでrkセグメントに従って、毎回rkに等しいセグメントだけを並べ替えると、毎回の並べ替えの長さはn/logと考えることができますか?

#include
#include
#include
#include
#include
#include
#include
#include
#define For(i,j,k)	for(int i=j;i<=k;++i)
#define Dow(i,j,k)	for(int i=k;i>=j;--i)
#define ll long long
#define inf 1e9
using namespace std;
inline int read()
{
	int t=0,f=1;char c=getchar();
	while(!isdigit(c))	{if(c=='-')	f=-1;c=getchar();}
	while(isdigit(c))	t=t*10+c-'0',c=getchar();
	return t*f;
}
inline void write(int x){if(x>=10)	write(x/10);putchar(x%10+'0');}
inline void writeln(int x){write(x);puts("");}
inline void write_p(int x){write(x);putchar(' ');}
int sa[2000001],n,rk[2000001],rk2[2000001],tmp[2000001];
char s[2000001];
inline bool cmp(int x,int y)
{
	return rk[x]==rk[y]?rk2[x]
区間の最値RMQ学習ノートを解く(オンラインSTアルゴリズム)
Head First設計モード学習ノート(九)テンプレート方法モード