首页 > 代码库 > uva 11475 - Extend to Palindrome(KMP)
uva 11475 - Extend to Palindrome(KMP)
题目链接:uva 11475 - Extend to Palindrome
题目大意:给定一个字符串,输出最少需要添加多少个字符使得字符串变成回文串。
解题思路:以字符串的转置做KMP,然后用原串匹配即可,最后匹配长度即为重复长度。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
char s[maxn], t[maxn];
int n, jump[maxn];
void get_jump () {
int p = 0;
for (int i = 2; i <= n; i++) {
while (p && s[p + 1] != s[i])
p = jump[p];
if (s[p + 1] == s[i])
p++;
jump[i] = p;
}
}
int find () {
int p = 0;
for (int i = 1; i <= n; i++) {
while (p && s[p + 1] != t[i])
p = jump[p];
if (s[p + 1] == t[i])
p++;
}
return p;
}
int main () {
while (scanf("%s", s + 1) == 1) {
printf("%s", s+1);
n = strlen(s + 1);
for (int i = 1; i <= n + 1; i++)
t[i] = s[i];
reverse(s + 1, s + n + 1);
get_jump();
int k = find();
for (int i = k + 1; i <= n; i++)
printf("%c", s[i]);
printf("\n");
}
return 0;
}
uva 11475 - Extend to Palindrome(KMP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。