UVA 11475 回文串
题目就是给你一个字符串 叫你求构造成一个回文串我们可以把原来的翻转一下 求拓展kmp 减去最大的贡献 就是要增加的长度 那么可以得到答案了#include <cstdio>#include <cstring>#include <algorithm>#include <cstring>#i
·
我们这样想
你把原串翻转放在前面 拼接原串
这样你求Next[len]就是对整个回文串的贡献后缀 比如 abbc 拼接后为cbbaabbc Next[len]为1 其实也就是这个原来的后缀c 会提供一个贡献 你就不用加这个c了 而是依次加上b b a
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 1000024;
int Next[MAX_N];
char str[MAX_N],mo[MAX_N];
int n2;
void getnext(){
int i =0,j = -1;
while(i<n2){
if(j==-1||mo[i]==mo[j]) {++i,++j,Next[i]=j;}
else j =Next[j];
}
return ;
}
int main(){
while(scanf("%s",str)!=EOF){
int len = strlen(str);
n2 = 0;
for(int i=0;i<len;i++)
mo[n2++] = str[len-i-1];
mo[n2++] = '#';
for(int i = 0;i<len;++i)
mo[n2++] = str[i];
mo[n2] = '\0';
Next[0] = -1;
getnext();
int ans_len = Next[n2];
printf("%s",str);
for(int i = len-ans_len-1;i>=0;i--)
printf("%c",str[i]);
printf("\n");
}
return 0;
}
更多推荐
已为社区贡献2条内容
所有评论(0)