题解：AT_abc398_f [ABC398F] ABCBA

四倍经验：P9606，UVA11475，SP4103。

题目大意

给出一个字符串

s

，求以

s

为前缀的最短回文串。

1 \le |s| \le 5 \times 10 ^ 5

。

题目分析

解法一：KMP

分析

设

s

反转后为

t

。此时，

t + s

必为回文串。接下来我们让这个回文串最短。

拿

s = \texttt{TREE}

举例，此时

t = \texttt{EERT}

，那么

t + s = \texttt{EERTTREE}

，那么这里的两个

\texttt{E}

就是多余的，我们可以把这两个删掉，而这两个就是

t + s

的最长相同前缀后缀，那 KMP 即可解决。

code

CPP

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 5e5 + 5;
int p[N << 1];
int main()
{
	string s; cin >> s;
	string t = s;
	reverse(t.begin(), t.end());
	string b = ' ' + t + ' ' + s;
	p[1] = 0;
	int l = b.size() - 1;
	for (int i = 1, j = 0; i < l; i++)
	{
		while (j && b[j + 1] != b[i + 1]) j = p[j];
		if (b[j + 1] == b[i + 1]) j++;
		p[i + 1] = j;
	}
	int k = p[l];
	string ans = s; l = t.size();
	for (int i = k; i < l; i++) ans += t[i];
	cout << ans << endl;
	return 0;
}

题解：AT_abc398_f [ABC398F] ABCBA

文章操作

题目大意

题目分析

解法一：KMP

分析

code

相关推荐

评论

题解：AT_abc398_f [ABC398F] ABCBA