| 比赛 |
2026.1.3 |
评测结果 |
AAAWAAWWWW |
| 题目名称 |
KMP |
最终得分 |
50 |
| 用户昵称 |
彭欣越 |
运行时间 |
0.791 s |
| 代码语言 |
C++ |
内存使用 |
9.69 MiB |
| 提交时间 |
2026-01-03 11:27:21 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
int n,a[N];
int idx,kmp[N];
char c[N];
int main () {
freopen("kmpp.in","r",stdin);
freopen("kmpp.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n;
for (int i=1;i<=n;i++) {
cin >> a[i];
if (a[i]-a[i-1]>=2||(i==1&&a[i]==1)) {
cout << "Impossible" <<endl;
return 0;
}
if (i==1) {
c[i]='a';
continue;
}
if (a[i]==0) {
if (c[1]!=c[i-1]||i-1==1) {
c[i]=char((int)c[1]+1);
}else{
c[i]=char((int)c[2]+1);
}
}else c[i]=c[a[i]];
//cout << c[i] <<endl;
}
int len=strlen(c+1);
for (int i=2;i<=len;i++) {
while (idx&&c[i]!=c[idx+1]) idx=kmp[idx];
if (c[idx+1]==c[i]) idx++;
kmp[i]=idx;
}
for (int i=1;i<=len;i++) {
if (kmp[i]!=a[i]) {
cout << "Impossible" <<endl;
return 0;
}
}
for (int i=1;i<=len;i++) cout << c[i];
return 0;
}