Cod sursa(job #2763052)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 11 iulie 2021 13:05:48
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <istream>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[2000005];
int v[2000005];
int main()
{
    int n,i,mijpalc=0,lpalc=0,j,maxim=-1,sume=0;
    fin.getline(s,2000005);
    n=strlen(s);
    for(i=n-1;i>0;i--)
    {
        s[i*2+1]=s[i];
        s[i*2]='*';
    }
    s[0]='#';
    s[2*n]='$';
    for(j=1;j<2*n;j++)
    {
        if(j>mijpalc+lpalc)
        {
            mijpalc=j;
            for(lpalc=1;lpalc<=n && lpalc<=j;lpalc++)
                if(s[lpalc+mijpalc]!=s[mijpalc-lpalc])
                    break;
                lpalc--,v[j]=lpalc;
        }
        else
        {
           /// capat stanga palogl > capat stanga palindrom mare
          /// 2*mij-j-v[2*mij-j]> mijpalc-lpalc
          if(2*mijpalc-j-v[2*mijpalc-j]>mijpalc-lpalc)
            v[j]=v[2*mijpalc-j];
          else
          {
              lpalc=mijpalc+lpalc-j;
              mijpalc=j;
              while(s[mijpalc+lpalc+1]==s[mijpalc-lpalc-1])
              {
                  lpalc++;
              }
              v[j]=lpalc;
          }
        }
    }
    for(i=1;i<2*n;i++)
        if(i%2==0)
            {
                v[i]=(v[i]+1)/2;
            }
        else
        {
            v[i]=v[i]/2;
            v[i]=v[i]+1;
        }
    for(i=1;i<2*n;i++)
    sume+=v[i];
    fout<<sume;
    return 0;
}