Pagini recente » Cod sursa (job #2851701) | Cod sursa (job #2618589) | Cod sursa (job #489913) | Cod sursa (job #545337) | Cod sursa (job #2503117)
#include <iostream>
#include <fstream>
#define MAX 400010
using namespace std;
int n,aa;
string s,s2;
int pi[MAX];
bool palindrom(string s){
for(int i=s.size()-1;i>=0;i--)
if(s[i]!=s[s.size()-1-i])return 0;
return 1;
}
void calc_pi(){
pi[0]=0;
int la=0;
for(int i=1;i<2*n;){
if(s2[i]==s2[la])pi[i++]=++la;
else
if(la!=0)la=pi[la-1];
else pi[i++]=0;
}
}
int main()
{
ifstream f ("palindrom.in");
ofstream g ("palindrom.out");
f>>s; n=s.size();
if(palindrom(s))g<<s<<'\n';
else {
for(int i=n-1;i>=0;i--)s2=s2+s[i];
s2+=s;
// cout<<s2<<'\n';
calc_pi();
aa=pi[2*n-1];
// for(int i=0;i<2*n;i++) cout<<pi[i]<<" ";
if(aa==0)aa=1;
// cout<<aa;
for(int i=0;i<n-aa;i++)g<<s[i];
for(int i=n-aa;i<n;i++)g<<s[i];
for(int i=n-aa-1;i>=0;i--)g<<s[i];
}
f.close ();
g.close ();
return 0;
}