【UVA-11475】Extend to Palindrome • TonyYin's Blog

题意#

对于一个字符串 $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;
}

cpp