4974: 字符串大师
Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 310 Solved: 155
[Submit][Status][Discuss]
Description
一个串T是S的循环节，当且仅当存在正整数k，使得S是T^k(即T重复k次)的前缀，比如abcd是abcdabcdab的循环节
。给定一个长度为n的仅由小写字符构成的字符串S，请对于每个k(1<=k<=n)，求出S长度为k的前缀的最短循环节的
长度per_i。字符串大师小Q觉得这个问题过于简单，于是花了一分钟将其AC了，他想检验你是否也是字符串大师。
小Q告诉你n以及per_1,per_2,...,per_n，请找到一个长度为n的小写字符串S，使得S能对应上per。
Input
第一行包含一个正整数n(1<=n<=100000)，表示字符串的长度。
第二行包含n个正整数per_1,per_2,...per_n(1<=per_i<=i)，表示每个前缀的最短循环节长度。
输入数据保证至少存在一组可行解。
Output
输出一行一个长度为n的小写字符串S，即某个满足条件的S。
若有多个可行的S，输出字典序最小的那一个。
顾忌于HDM的毒奶，我决定去复习KMP算法。。。好吧，我承认，这是我人生中第一次把kmp看懂个八九成。。。
回道题目，我们看了题解后不难发现，对于每个i有：next[i]=i-pre[i]。这个画一个简图就可以证明，接着就按这个next数组跑kmp咯。如果当前i的next不为0，那么就直接把之前的元素复制过来，否则就像跑kmp那样把有可能使其next不为零的字母都记录下来，贪心地找最小的没出现过的字母即可。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000+10
int n,a[MAXN],vis[],per[MAXN],next[MAXN];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&per[i]);
next[i]=i-per[i];
}
a[]=;
next[]=-;
for(int i=;i<=n;i++)
if(next[i]!=)
a[i]=a[next[i]];
else{
memset(vis,,sizeof(vis));
int k=next[i-]+;
while(k){
vis[a[k]]=;
k=next[k-]+;
}
for(int j=;j<=;j++)
if(!vis[j]){a[i]=j;break;}
}
for(int i=;i<=n;i++)printf("%c",a[i]+'a'-);
return ;
}