题目概述

如果 $S$ 是 $T$ 重复无数次之后的前缀，那么 $T$ 就是 $S$ 的循环节，现在给出一个串每个前缀 $i$ 的最短循环节 $per_i$ 表示前缀 $per_i$ 是前缀 $i$ 的循环节，构造一个字典序最小的串满足 $per$ 。

解题报告

前缀 $i$ 的最短循环节就是 $border$ 也就是 $i-fail_i$ ，所以给出 $per$ 也就是给出了 $fail$ ，那么就是用 $fail$ 构造原串。可以这样搞：对于每个位置枚举这个位置选的字符，然后跑 $fail$ 验证是否满足。

看起来没毛病，实际上很奇怪，因为只有在一个串的时候KMP的复杂度是正常的，这样枚举串复杂度分析就跪了。所以应该这样做：因为第 $i$ 个会跳到 $fail_i$ ，所以路上的所有字符都不能选（否则会在路上停下来），那么就每次跳 $fail$ 直到跳到 $fail_i$ ，把路上经过的字符都标记一下，如果最后匹配到了，说明 $i$ 和匹配到的地方字符相同，否则就应该选一个路上没出现过的字符。

示例程序

#include<cstdio>
using namespace std;
const int maxn=100000,maxi=26;

int n,fai[maxn+5],ti,vis[maxi];char ans[maxn+5];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&fai[i]),fai[i]=i-fai[i];
    for (int i=1,j=fai[0]=-1;i<=n;i++){
        ti++;while (fai[i]!=j+1) vis[ans[j+1]-'a']=ti,j=fai[j];
        j++;if (j) ans[i]=ans[j]; else for (int k=0;k<maxi;k++) if (vis[k]<ti) {ans[i]='a'+k;break;}
    }puts(ans+1);return 0;
}