Cod sursa(job #3224430)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 15 aprilie 2024 13:12:01
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
//https://www.infoarena.ro/problema/pscpld
#include <bits/stdc++.h>
using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

int d[1000000];
int main()
{
    int ex=0,rez=1,i,ssize;
    string s;
    fin>>s;
    ssize=s.size();
    ssize=ssize*2-1;
    d[0]=1;
    for(i=1;i<ssize;++i)
    {
        if(i<ex+d[ex])//daca este mai mic decat ex
        {
            d[i]=min(d[ex*2-i],d[ex]+ex-i);
        }
        else//alfel
        {
            if(i&1)
            {
                d[i]=0;
            }
            else
            {
                d[i]=1;
            }
        }
        while((i+d[i]<ssize-1)&&(i-d[i]>0))//ma duc in dreapra si stinga sa vad daca ma mai pot duce
        {
            if(s[(i+d[i]+1)/2]!=s[(i-d[i]-1)/2])//daca sunt diferite
            {
                break;
            }
            d[i]+=2;
        }
        rez+=(d[i]+1)/2;//pun rezultatul
        if(i+d[i]>ex+d[ex])//daca este mai mare pun ex
        {
            ex=i;
        }
    }
    fout<<rez;

    return 0;
}