马拉车算法 O（n）复杂度内处理回文

60 阅读 0 评论 40 点赞

我是靠谱客的博主直率秋天，最近开发中收集的这篇文章主要介绍马拉车算法 O（n）复杂度内处理回文，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Holidays are almost over and our dear friend Mr. Potato Head wants to enjoy his last days of vacations with different fun activities like solving equations, calculating areas of figures, among others.

Currently, he is playing with different strings, although he finds that most of strings are boring non-palindromic strings. That is why Mr. Potato Head will transform any string into a palindrome inserting characters at the end of the corresponding string.

However, Mr. Potato Head does not want to spend his lasts days of holidays only inserting characters in strings, so he will insert the minimum possible of characters to convert the boring non-palindromic string into a fun palindromic one.

Can you guess the fun strings Mr. Potato Head created from boring ones?

Input
Input consists of a single line with a non-empty string without spaces.

The length of the string is at most $ $5000$ $.

Output
Print one single line with the string after the changes of Mr. Potato Head.

Examples
Input
helloworld
Output
helloworldlrowolleh
Input
anitalavalatina
Output
anitalavalatina
Note
A palindrome is a string that reads the same backwards as forwards

题目大致意思是只能在字符串后面插入字母，问最少插入次数使他成为回文串，思路是用马拉车算法找出每个位置的最大半径，如果半径加上他的位置刚好等于末尾，就记录这个位置，再输出原先字符串+上不重复的字符串的反向。记得用空格，因为题目说里面不含空格，N开两倍，因为要马拉车要扩增一倍，p[i]=mx>i?min(p[2*id-i],mx-i):1;马拉车算法的精髓就是这一句，id代表最大对称点，mx代表能向右延伸的最大位置，2*id-i代表i对于id的对称点，如果，i在mx里面的话，如果对称点的对称半径没有超过i到mx的距离，就用它的，否则用mx-i代替，不在mx里就把p[i]换成1，老老实实去暴力能否扩增，mx记得更新。P[]数组代表每个点的最大半径（算上自己），mx不含在最大回文字符串里面，所以mx-i不用加一，最后最长的回文串是len-1，一般初始化string +"@“和”#"就行了，

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
string s;
const	int N=5010;
int p[N*2];
string t;
string malache()
{
t+=' ';
t+=' ';
for(int i=0;i<s.size();i++)
{
t+=s[i];
t+=' ';
}
int id=0,mx=0,pos=0,len=0;
for(int i=1;i<t.length();i++)
{
p[i]=mx>i?min(p[2*id-i],mx-i):1;
while(t[i-p[i]]==t[i+p[i]])	++p[i];
if(p[i]+i>mx)
{
mx=p[i]+i;
id=i;
}
if(p[i]>len)
{
len=p[i];
pos=i;
}
}
return s.substr((pos-len)/2,len-1);
}
int main()
{
cin>>s;
string ans=malache();
int pos=0;
cout<<t<<endl;
for(int i=1;i<t.size();i++)
if(i+p[i] -1==t.size()-1)
//-1是因为p[i]长度还包括了自身
{
pos=i;
break;
}
;
}