AT_abc398_f [ABC398F] ABCBA 题解

## 题目大意
给定一个字符串 $S$，请你在 $S$ 后面追加最少的字符，使得 $S$ 是一个回文串。

## 解题思路
定义 $|S|$ 为字符串 $S$ 的长度。
首先我们考虑找到一个最靠前的下标 $i$（$0 \leq i < |S|$），使得以 $S_i$ 为回文中点可以构成一个回文串，由于题目让我们把 $S$ 补全成一个回文串，我们在找回文中点的时候只需要满足以 $|S| - i$ 为回文长度，$i$ 为回文中心的子串是回文串即可。

于是我们可以用 Manacher 算法完成回文子串的寻找，听说可以用 KMP 算法，但是我不会。

CODE：
```cpp
#include <bits/stdc++.h>
using namespace std;
int p[22000010];
//哈哈哈，manacher
int main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	string s, a = "";
	cin >> s;
	// 构建新的字符串，添加 # 作为分隔符
	for (int i = 0; i < s.size(); i++) {
		a += s[i];
		a += "#";
	}
	a = "#" + a;  // 在最开始加入 #，处理奇偶长度回文的情况
	// 初始化
	int r = -1, c = -1, ans = -1;  // 右边界, 中心位置, 回文半径的最大值
	for (int i = 1; i < a.size(); i++) {
		// 计算镜像点
		int j = 2 * c - i;
		if (i < r) {
			p[i] = min(r - i, p[j]);  // 直接延续之前的回文信息
		} else {
			p[i] = 1;  // 最小回文长度是 1
		}
		// 试图扩展回文
		while (i - p[i] >= 0 && i + p[i] < a.size() && a[i - p[i]] == a[i + p[i]]) {
			p[i]++;
		}
		// 更新右边界和中心位置
		if (i + p[i] - 1 > r) {
			r = i + p[i] - 1;
			c = i;
		}
	}
	for (int i = 0; i < a.size(); i++) {
		if (p[i] - 1 == a.size() - i - 1) {
			ans = i;
			break;
		}
	}
	if (ans == -1) {
		cout << s;
		for (int i = s.size() - 2; i >= 0; i--) {
			cout << s[i];
		}
	} else {
		cout << s;
		for (int i = s.size() - p[ans]; i >= 0; i--) {
			cout << s[i];
		}
	}
	return 0;
}
```

正在渲染内容...