PKU 3058 Decompression

問題概要

次のような圧縮方法を考える。
文字列に対しi文字ずつシフトしたものを全てつくり、それを辞書順に並び替える。
その後、全てのものについて最後の一文字をつなげる。
例：LEIDEN.

.LEIDEN
DEN.LEI
EIDEN.L
EN.LEID
IDEN.LE
LEIDEN.
N.LEIDE

なので
NILDE.Eになる。

その後で、連続する文字を、"その文字"+"連続する数"に置き換える。
この圧縮後の文字列が与えられた時、元の文字列を求めよ。元の文字列の最後は"."である。

解法

いわゆるブロックソート（知らない人はwikipedia参照）

まずは与えられた文字の"連続する数"を展開する。
展開後の文字列は最大100万文字なのでメモリ上にベタに展開して大丈夫。

展開後の文字列をソートすれば、上表における左端の文字列が得られる。
テーブルの「右端の文字」の（圧縮前の文字列における）次の文字はテーブルのその行の「左端の文字」であること、
更に元の文字列の最後はピリオドであることから元の文字列を復元できる。

ソースコード

char str[1000001],ans[1000001];
pair<char,int> p[1000001];
int idx[1000001],len;

int main()
{
	int n; scanf("%d",&n);
	rep(i,n)
	{
		scanf("%s",ans);
		int l1=strlen(ans),times=0,lastj=0;
		len=0;
		rep(j,l1)
		{
			if(j==l1-1||!isdigit(ans[j+1]))
			{
				if(times==0)times=1;
				while(times--)
				str[len++]=ans[lastj];
				times=0; lastj=j+1;
			}
			else times*=10,times+=ans[j+1]-'0';
		}
		str[len]=0;
		
		rep(j,len)p[j].first=str[j],p[j].second=j;
		sort(p,p+len);
		rep(j,len)idx[p[j].second]=j;
		
		ans[len]=0; ans[len-1]='.';
		int cur=0;
		rep(j,len-1)
		{
			ans[len-2-j]=str[cur];
			cur=idx[cur];
		}
		puts(ans);
	}
	
	return 0;
}