1699: 回文串问题
时间限制: 1 Sec 内存限制: 128 MB 提交: 22 解决: 3 [提交][状态][讨论版]题目描述
还是回文串问题，字符串是啥，大家应该都知道，就是满足 S[i] = S[L - i + 1] (1 <= i <= L)的串，现在遇到了一个问题，就是想问你一个字符串最少在后边加几个字符可以形成一个回文串，并最后输出形成的回文串
输入
输入包括多组数据，每组数据包含一个字符串
输出
输出转换后的回文字符串
样例输入
add cigartragic dxhisgirl acaba abczyxyz
样例输出
adda cigartragic dxhisgirlrigsihxd acabaca abczyxyzcba
题解：manacher,随着数组往前走，更新m和r，l没什么用，其实就是2*m-r，所以只需要管m和r就好了，由于多了"#"所以此时的值就是回文长度；只需要计算结尾处的最长回文就好了，以前做过类似题。。。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
#define T_T while(T--)
#define F(i,s,x) for(i=s;i<x;i++)
const double PI=acos(-1.0);
typedef long long LL;
const int MAXN=100010;
char a[MAXN],s[MAXN<<1];
int p[MAXN<<1];
int manacher(){
int len=strlen(s),i,l=1,r=1,mid=1,ans=0;
mem(p,0);
p[0]=p[1]=1;
F(i,2,len){
// if(r>i)p[i]=min(p[2*mid-i],r-i);
// else//仔细想了想，这段不要就可以，只不过可能耗时了一些；但是本校oj数据弱，就ac了。。。
p[i]=1;
while(s[i+p[i]]==s[i-p[i]])p[i]++;
if(p[i]+i>r)r=p[i]+i,mid=i;
if(r==len)ans=max(ans,p[i]);
}
return ans-1;
}
int main(){
while(~scanf("%s",a)){
int len=strlen(a);
s[0]='@';
int i;
F(i,0,len){
s[i*2+1]='#';
s[i*2+2]=a[i];
}
s[len*2+1]='#';s[len*2+2]=' ';
int ans=manacher();
// printf("%d
",ans);
printf("%s",a);
for(i=len-ans-1;i>=0;i--)printf("%c",a[i]);puts("");
}
return 0;
}
kmp一遍a;
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
const int INF=0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define P_ printf(" ")
#define T_T while(T--)
#define F(i,s,x) for(i=s;i<x;i++)
const double PI=acos(-1.0);
typedef long long LL;
const int MAXN=100010;
char a[MAXN],b[MAXN];
int p[MAXN];
void getp(char *s){
int len=strlen(s);
int i=0,j=-1;
p[0]=-1;
while(i<len){
if(j==-1||p[i]==p[j]){
i++;j++;
p[i]=j;
}
else j=p[j];
}
}
int kmp(char *s,char *ms){
int len=strlen(ms);
getp(s);
int i=0,j=0;
while(i<len){
if(j==-1||ms[i]==s[j]){
i++;j++;
}
else j=p[j];
}
return j;
}
int main(){
while(~scanf("%s",a)){
memcpy(b,a,sizeof(a));
int len=strlen(a);
for(int i=0,j=len-1;i<len;i++,j--)b[i]=a[j];
int ans=kmp(b,a);
printf("%s",a);
for(int i=len-1-ans;i>=0;i--)printf("%c",a[i]);puts("");
}
return 0;
}