Cod sursa(job #2503117)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 2 decembrie 2019 15:29:43
Problema Prefix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#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;
}