UVA – 11475 – Extend to Palindrome

题意

对于一个字符串 $s$,求出一个尽可能短的回文字符串 $s^{*}$,同时使得 $s$ 是 $s^{*}$ 的前缀。

$|s|\leq 10^5$.

分析

前置知识:Manacher – OI Wiki,,题解同步发表于 TonyYin’s Blog

首先,先考虑如何满足 $s$ 是 $s^{*}$ 的前缀,且 $s^{*}$ 是回文串这两个条件

经过简单分析可以得到,$s^{*}$ 回文中心左侧一定都与 $s$ 的前缀相同。

因此只需要找到最小的 $i$,其回文半径可以延续到串末即可。

形式化地,要找到最小的 $i$ 满足 $s[2\times i-len]\sim s[i]\sim s[len]$ 为回文串。

实现

通过 $\rm{Manacher}$ 算法解决问题。

在进行 $\rm{Manacher}$ 的过程中,只要当前点 $i$ 的回文半径可以延续到串末,$i$ 即为 $s^{*}$ 的回文中心。

找到中心之后,把 $s^{*}$ 还原出来即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXLEN = 1e5 + 10;
char in[MAXLEN], s[MAXLEN << 1];
int len;
void init() {
	int lenin = strlen(in); len = 0;
	s[++len] = '*'; s[++len] = '|';
	for(int i = 0; 
        i < strlen(in); i++) {
		s[++len] = in[i]; s[++len] = '|';
	}
}
int p[MAXLEN << 1];//以i为中心的最大回文半径
int main() {
	while(scanf("%s", in) != EOF) {
		int ans = 0;
		int mx = 0, id = 0; init();
		for(int i = 1; i <= len; i++) {
			if(i < mx) p[i] = min(mx - i, p[2 * id - i]);
			else p[i] = 1;
			while(s[i + p[i]] == s[i - p[i]]) p[i]++;
			if(i + p[i] >= mx) {
				id = i; mx = i + p[i];
			}
			if(mx >= len) {
				ans = i;
				break;
			}
		}
		for(int i = 2; i <= ans; i++) if(s[i] != '|') putchar(s[i]);
		for(int i = ans - 1; i >= 2; i--) if(s[i] != '|') putchar(s[i]);
		putchar('\n');
	}
	return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();