字符串题
一个串 \(T\) 是 \(S\) 的循环节，当且仅当存在正整数 \(k\) ，使得 \(S\) 是 \(T\) 重复 \(k\) 次形成的字符串的前缀，比如
abcd是abcdabcdab的循环节。已知 \(S\) 是一个长度为 \(n\) 的仅由小写字符构成的字符串， \(S\) 的长度为 \(i\) 的前缀的最短循环节的长度 \(pre_i\) 。
告诉你 \(n\) 以及 \(pre_{1\cdots n}\) ，请找到一个长度为 \(n\) 的小写字符串 ，使得 \(S\) 能对应上 \(pre\) 数组。
题解
结论：对于一个字符串，其最短循环节为 \(n-fail_n\) .
那么， \(i-pre_i=fail_i\) .
以下分为两种情况考虑：
- \(fail_i \neq0\)
- 此时 \(fail_i\) 表示 \(1\cdots i\) 中前缀与后缀相等部分，则 \(a_i\equiv a_{fail_i}\).
- \(fail_i=0\)
- 我们考虑 kmp 的过程：
while(j && b[j+1] != b[i]) j = fail[j];j += b[j+1] == b[i];
- 如果 \(fail_i=0\)，那么意味着随着 \(fail\) 向前跳动，\(b[j+1]\neq b[i]\) 恒成立。
- 所以，在所有 \(b_{j+1}\) 未出现过的字符中，找到字典序最小的即可。
代码
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 1e5+5,mod = 1e9+7;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret=0;char ch=‘ ‘,c=getchar();
while(!(c>=‘0‘&&c<=‘9‘))ch=c,c=getchar();
while(c>=‘0‘&&c<=‘9‘)ret=(ret<<1)+(ret<<3)+c-‘0‘,c=getchar();
return ch==‘-‘?-ret:ret;
}
int n;
int pre[N],fail[N];
char a[N];
bool vis[300];
signed main(){
n = read();
for(int i = 1 ; i <= n ; i ++)
pre[i] = read(),
fail[i] = i - pre[i];
// for(int i = 1 ; i <= n ; i ++)printf("fail[%d] = %d\n",i,fail[i]);
a[1] = ‘a‘;
fail[0] = -1;
for(int i = 2 ; i <= n ; i ++){
if(fail[i])
a[i] = a[fail[i]];
else{
int j = fail[i-1];
while(~j) vis[(int)a[j+1]] = 1 , j = fail[j];
for(int k = ‘a‘ ; k <= ‘z‘ ; k ++)
if(!vis[k]) {a[i] = k;break;}
else vis[k] = 0;
}
}
puts(a+1);
return 0;
}