首页 > 代码库 > UVA 11475 Extend to Palindrome KMP
UVA 11475 Extend to Palindrome KMP
题目链接：https://vjudge.net/problem/UVA-11475
题意：
给你一个串S
你可以在结尾补充任意数量字母，问最少数量使得新串是回文串
题解：
KMP
将S串倒置跑KMP
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define pii pair<int,int>#define MP make_pairtypedef long long LL;typedef unsigned long long ULL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 2e5+10, M = 1e3+20,inf = 2e9;int fail[N];char a[N],b[N];int len;void build_fail() { memset(fail,-1,sizeof(fail)); int j = -1; fail[0] = -1; for(int i = 1; i < len; ++i) { while(j!=-1 && b[i] != b[j+1]) j = fail[j]; if(b[j+1] == b[i]) j++; fail[i] = j; }}int kmp() { int j = -1; for(int i = 0; i < len; ++i) { while(j!=-1 && a[i]!=b[j+1]) j = fail[j]; if(b[j+1] == a[i]) j++; } return j+1;}int main() { while(scanf("%s",a)!=EOF) { len = strlen(a); for(int i = 0; i < len; ++i) b[len - i - 1] = a[i]; build_fail(); cout<<a; for(int i = kmp(); i < len; ++i) printf("%c",b[i]); printf("\n"); } return 0;}
UVA 11475 Extend to Palindrome KMP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。