题解：AT_abc398_f [ABC398F] ABCBA
ljk8886
·
·
题解
题目传送门 AT
四倍经验：P9606，UVA11475，SP4103。
题目大意
给出一个字符串 s，求以 s 为前缀的最短回文串。
## 题目分析
### 解法一：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;
}
```