BZOJ4319 cerc2008 Suffix reconstruction 字符串 SA

原文链接http://www.cnblogs.com/zhouzhendong/p/9016336.html

题目传送门 - BZOJ4319

题意

　　给出一个$1,2,\cdots,n$的排列，第$i$项表示$SA[i]$。

　　让你构造一个只含有小写字母的字符串，使其$SA$数组为输入的值。或者输出无解。

　　$n\leq 5\times  10^5$

题解

　　首先，我们预处理出所有的$rank[i]$。

　　然后我们枚举$i$。

　　考虑给第$SA[i]$个位置插入字符。

　　给$SA[i]$处插入的字符必然不小于$SA[i-1]$处的字符。

　　那么如何判断是否要变大？

　　考虑如果$s_{_{SA[i]}}=s_{_{SA[i-1]}}$，那么我们需要比较的是$rank[SA[i]+1]$和$rank[SA[i-1]+1]$。

　　为了保证$rank[SA[i]]>rank[SA[i-1]]$，则当$rank[SA[i]+1]<rank[SA[i-1]+1]$时，我们给$s_{_{SA[i]}}$取的值要比$s_{_{SA[i-1]}}$大$1$。

　　最后看看需要的字符集大小判断是否无解即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=500005;

int n,SA[N],rank[N],a[N];

int main(){

	scanf("%d",&n);

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

		scanf("%d",&SA[i]);

		rank[SA[i]]=i;

	}

	rank[n+1]=0;

	int cnt=0;

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

		if (rank[SA[i]+1]<rank[SA[i-1]+1])

			cnt++;

		a[SA[i]]=cnt;

	}

	if (cnt>=26)

		puts("-1");

	else

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

			putchar(a[i]+'a');

	return 0;

}