E - Extend to Palindrome manacher+贪心
Source
My Solution
题意:给出一个字符串,在末尾添加尽可能少的字符串,使这个新字符串为回文串,输出新字符串。
manacher+贪心
先用manacher O(n)的跑出原字符串的以每个i为中心的回文子串,
然后应该自己得出的一个manacher的结论if(len[i + j] >= (j - i)/2 + 1) 则字符串s[i......j]为回文子串。
也就是从原串的右边开始,向左跑,找到以sz-1为右端点的最大回文子串,标记为ans开始,则输出原串后,从ans-1开始到0按照顺序每个字符依次输出。
复杂度 O(n)
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;
int len[2*maxn];
char str[maxn];
void manacher(int n)
{
int p, q, r;
len[0] = 1;
for(int i = 1, j = 0; i < (n << 1) - 1; i++){ p = i >> 1, q = i - p, r = ((j + 1) >> 1) + len[j] - 1;
len[i] = r < q ? 0 : min(r - q + 1, len[(j << 1) - i]); while(p > len[i] - 1 && q + len[i] < n && str[p - len[i]] == str[q + len[i]]) len[i]++; if(q + len[i] - 1 > r)
j = i;
}
}
int main()
{
#ifdef LOCAL
freopen("e.txt", "r", stdin);
//freopen("e.out", "w", stdout);
#endif // LOCAL
int sz, i, j, ans;
while(scanf("%s", str) != EOF){
sz = strlen(str); ans = sz - 1;
manacher(sz);
for(i = sz - 2, j = sz - 1; i >= 0; i--){
if(len[i + j] >= (j - i)/2 + 1){
ans = i;
}
}
printf("%s", str);
for(i = ans - 1; i >= 0; i--) putchar(str[i]);
putchar('n');
}
return 0;
}
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
如经许可后转载,请注明出处:https://prolightsfxjh.com/article/uva-11475-extend-to-palindrome-manacher/
共有 0 条评论