Cod sursa(job #2220039)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 10 iulie 2018 13:28:17
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#define MAX 1000010

using namespace std;

int n,ansf,sz;
int ansi[MAX],ansp[MAX];
string s;
void veri(int ind){
  for(int j1=ind-ansi[ind],j2=ind+ansi[ind];j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++)
    ansi[ind]++;
}
void verp(int ind){
  for(int j1=ind-ansi[ind],j2=ind+ansi[ind]+1;j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++)
    ansi[ind]++;
}

int main()
{
    ifstream f ("pscpld.in");
    ofstream g ("pscpld.out");
    f>>s;n=s.size();s="!"+s;
    ansi[1]=1;
    for(int i=2;i<=n;i++){
      if(ansi[i])continue;
      sz=0;
      for(int j1=i,j2=i;j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++,sz++);
      //cout<<sz<<" ";
      ansi[i]=sz;
      for(int j=1;j<=sz-1;j++)
        ansi[i+j]=min(ansi[i-j],sz-j),
        veri(i+j);
    }
    //cout<<'\n'; for(int i=1;i<=n;i++)cout<<ansi[i]<<" ";
    ansp[1]=((s[1]==s[2])?1:0);
    for(int i=2;i<=n;i++){
      if(ansp[i])continue;
      sz=0;
      for(int j1=i,j2=i+1;j1>=1&&j2<=n&&s[j1]==s[j2];j1--,j2++,sz++);
      ansp[i]=sz;
      for(int j=1;j<=sz-1;j++)
        ansi[i+j+1]=min(ansi[i-j],sz-j),
        veri(i+j+1);
    }
    //cout<<'\n'; for(int i=1;i<=n;i++)cout<<ansp[i]<<" ";
    for(int i=1;i<=n;i++)
      ansf+=ansi[i]+ansp[i];
    g<<ansf<<'\n';
    f.close();
    g.close();
    return 0;
}