Description：

给出 $n$ 和字符串前 $i$ 个字符的最小循环节 $per[i]$ 。要求构造出符合条件的字典序最小的小写字母字符串。

$1\leqslant n\leqslant 10^5$

Solution：

首先 $per[i]=i-nxt[i]$ ，也就是说我们实际上已知了 $nxt$ ，从前往后一位位考虑，如果 $nxt\ne 0$ ，那么我们就已经知道了这个字符是什么，否则的话，考虑 $KMP$ 算法的运行过程， $j$ 不断尝试加一，如果不能就跳 $nxt$ ，那么它在尝试添加当前字符的时候也跳过了一些字符，显然这一位的字符应该与那些都不同，于是贪心就好了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int per[MAXN],nxt[MAXN];

int cnt[26];

char c[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&per[i]);

	for(int i = 1;i <= n;++i)nxt[i] = i - per[i];

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

	{

		if(nxt[i] != 0)

		{

			c[i] = c[nxt[i]];

		}

		else

		{

			int cur = i - 1;

			while(cur)

			{

				++cnt[c[cur + 1]];

				cur = nxt[cur];

			}

			int pos = 0;

			while(cnt[pos] != 0)++pos;

			c[i] = pos;

			memset(cnt,0,sizeof(cnt));

		}

	}

	for(int i = 1;i <= n;++i)putchar(c[i] + 'a');

	return 0;

}