HDU - 2970 Suffix reconstruction

Discription

Given a text s[1..n] of length n, we create its suffix array by taking all its suffixes: s[1..n], s[2..n],...., s[n..n] and sorting them lexicographically. As a result we get a sorted list of suffixes: s[p(1)..n], s[p(2)..n],..., s[p(n)..n] and call the sequence p(1),p(2),...,p(n) the suffix array of s[1..n].

For example, if s = abbaabab, the sorted list of all suffixes becomes: aabab, ab, abab, abbaabab, b, baabab, bab, bbaabab and the suffix array is 4, 7, 5, 1, 8, 3,6, 2.

It turns out that it is possible to construct this array in a linear time. Your task will be completely different, though: given p(1), p(2), p(3),... , p(n) you should check if there exist at least one text consisting of lowercase letters of the English alphabet for which this sequence is the suffix array. If so, output any such text. Otherwise output -1.

Input

The input contains several descriptions of suffix arrays. The first line contains the number of descriptions t (t <= 100). Each description begins with a line containing the length of both the text and the array n (1 <= n <= 500000). Next line contains integers p(1), p(2), ... ,p(n). You may assume that 1 <= p(i) <= n and no value of p(i) occurs twice. Total size of the input will not exceed 50MB.

Output

For each test case
If there are multiple answers, output the smallest dictionary order in the given suffix array. In case there is no such text consisting of lowercase letters of the English alphabet, output -1.

Sample Input

6

2

1 2

2

2 1

3

2 3 1

6

3 4 5 1 2 6

14

3 10 2 12 14 5 13 4 1 8 6 11 7 9

7

5 1 7 4 3 2 6

Sample Output

ab

aa

bab

bcaaad

ebadcfgehagbdc

bcccadc

    首先如果字符集无限大的话，答案是很好构造的。但是字符集有限制的话，我们就必须尽量压缩字符。
    比如，ac可以被替换成ab;最小的字符应该是a;还有最重要的一点:(假设rank[i]是从第i位开始的后缀的排名，越小越靠前)如果我们顺着sa数组指向的后缀扫的话，后缀首字母肯定是连续一段的a,然后连续一段的b....我们判断s[sa[i]]是否可以等于s[sa[i-1]]的时候，只需要判断rank[sa[i]+1]是否大于rank[sa[i-1]+1]就可以了。
    学过后缀数组sa的都知道，我们通过sa是可以复原rank的，理论上说rank就是sa的一个逆置换(sa[i]是排名第i的后缀的下标开始位置，rank[i]是开始位置是i的排名)，所以rank[sa[i]]=i。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=500005;

int T,n,sa[maxn],R[maxn];

char s[maxn];

bool flag;

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

int main(){

	T=read();

	while(T--){

		n=read(),flag=1;

		memset(s,0,sizeof(s));

		for(int i=1;i<=n;i++) sa[i]=read();

		for(int i=1;i<=n;i++) R[sa[i]]=i;

		s[sa[1]]='a',R[n+1]=0;

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

			if(R[sa[i-1]+1]<R[sa[i]+1]) s[sa[i]]=s[sa[i-1]];

			else s[sa[i]]=s[sa[i-1]]+1;

			if(s[sa[i]]>'z'){

				flag=0;

				break;

			}

		}

		if(flag) printf("%s\n",s+1);

		else puts("-1");

	}

}

巴特西

HDU - 2970 Suffix reconstruction

最新文章

热门文章