一個串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，輸出字典序最小的那一個。

Sample Input

5 1 2 2 2 5

Sample Output

ababb

題解：

　　規律都是自己手玩出來的，顯然看到這個題目就想著這個字符串是確定的，那么出來i號字符時，i前面都是處理出來的，而你又知道他的循環節，如果是小于i的話就直接對應上去就好了，如果=i，我只會n^2的，看了題解，只要模仿kmp，把每個可能的循環節枚舉出來，然后把字母判掉，之后最小的字母就是答案了。

?

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #define MAXN 100010 using namespace std; int a[MAXN],vis[28],n; char s[MAXN]; int main() { scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);s[1]='a';for(int i=2;i<=n;i++){if(i!=a[i]) s[i]=s[(i-1)%a[i]+1];else{memset(vis,0,sizeof(vis));int hh=i-1;while(hh!=a[hh]){hh=(hh-1)%a[hh]+1;vis[s[hh+1]-'a']=1;}for(int j=1;j<26;j++){if(!vis[j]) {s[i]='a'+j;break;}}}}s[n+1]=0;printf("%s",s+1);return 0; }

?

轉載于:https://www.cnblogs.com/renjianshige/p/7577526.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ 4974: 字符串大师的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。