题目描述：
给你一个字符串\(S\)，让你找一个长度最小的回文串\(P\)使得\(S\)是\(P\)的前缀
分析
我们能够构造出的最简单的回文串\(P\prime=S+reverse(S)\)
显然\(P\prime\)要尽量的小，那么\(S\)与\(reverse(S)\)就要尽可能地重叠
观察发现，尽可能重叠，其实是求得\(S\)末尾的最大的回文串
所以就有很多大佬用什么\(\text{manacher、SA}\)然而我都不会
那么我们重新想一想回文的定义，简单地说就是正着读，倒着读是一样的
那么我们可以把\(S\)反转一下得到\(S\prime\)，做一次\(\text{KMP}\)看在\(S\)左后一个字符的最大匹配
那么这个值就是\(S\)后缀的最长回文串，那么需要补上的字符串不就可以直接输出了？
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
char a[maxn], b[maxn];
int len, last, kmp[maxn];
inline void ac()
{
len = strlen(a + 1);
memset (kmp, 0, sizeof kmp);
memset (b, 0, sizeof b);
memcpy(b + 1, a + 1, len);
reverse(b + 1, b + len + 1);
last = 0;
for (int i = 2; i <= len; ++i) {
while (last && b[last + 1] != b[i]) last = kmp[last];
if (b[last + 1] == b[i]) ++last;
kmp[i] = last;
}
last = 0;
for (int i = 1; i <= len; ++i) {
while (last && a[i] != b[last + 1]) last = kmp[last];
if (a[i] == b[last + 1]) ++last;
}
printf ("%s%s\n", a + 1, b + last + 1);
}
int main()
{
while (~scanf("%s", a + 1))ac();
system("pause");
}
|