BZOJ4974 字符串大师【KMP】【贪心】

题意：

一个串T是S的循环节，当且仅当存在正整数k，使得S是T^k(即T重复k次)的前缀，比如abcd是abcdabcdab的循环节。给定一个长度为n的仅由小写字符构成的字符串S，请对于每个(1<=k<=n)，求出S长度为k的前缀的最短循环节的长度per_i。字符串大师小Q觉得这个问题过于简单，于是花了一分钟将其AC了，他想检验你是否也是字符串大师。小Q告诉你$n$以及$pe{r}_1,pe{r}_2,...,pe{r}_n$，请找到一个长度为n的小写字符串S，使得S能对应上per。输出字典序最小的那一个。

思路：

KMP算法中的一个性质：$i-Fail[i]$表示以i结尾的子串的最短循环节长度。所以$fail[i]=i-pe{r}_i$ 如果当前位置要推翻之前的循环节，即$fail[i+1]=0$，那么就沿着$fail$指针往回跳，往回跳时遇到的所有字符都不能用，由于要输出字典序最小的那个，就贪心地选没有遇到的字典序最小的字符。 若$fail[i+1]!=0$，那么当前字符就是$fail[i+1]$那个位置的字符。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 100010 int fail[MAXN],sta[MAXN],n; char ans[MAXN]; int main() { scanf("%d",&n); fail[0]=-1; for(int i=1,x;i<=n;i++) { scanf("%d",&x); fail[i]=i-x; } for(int i=0;i<n;i++) if(fail[i+1]) { ans[i]=ans[fail[i+1]-1]; int c=ans[i]-'a'; sta[i]=sta[fail[i]]|(1<<c); } else { int s,c; if(fail[i]==-1) s=0; else s=sta[fail[i]]; for(c=0;s&(1<<c);c++); ans[i]=c+'a'; sta[i]=sta[fail[i]]|(1<<c); } printf("%s\n",ans); }