Cod sursa(job #2784453)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 16 octombrie 2021 15:07:53
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int i,nr,center,sum,n,st,dr,radius,dp[2000005];
void pal(string s)
{
    n=s.size();
    string a;a[nr++]='*';
    for(i=0; i<n; i++)
    {
        a[nr++]=s[i];
        a[nr++]='*';

    }
    n=nr;
    dp[0]=1;
    center=0;
    radius=1;
    for(i=1; i<=nr; i++)
    {
        if(i>=center+radius)
        {
            st=i-1;
            dr=i+1;
            while(a[st]==a[dr]&&st>=0&&dr<nr)
            {
                st--;
                dr++;

            }
            center=i;
         radius=i-st-1;
            dp[i]=radius;
        }
        else
        {
            if(i-radius-dp[i-radius]<=center-radius)
            {
                st=i-1;
                dr=i+1;
                while(a[st]==a[dr]&&st>=0&&dr<nr)
                {
                    st--;
                    dr++;

                }
                center=i;
                radius=i-st-1;
                dp[i]=radius;
            }
            else dp[i]=dp[i-radius];
        }
    }
    for(i=1; i<nr; i++)sum+=(dp[i]+1)/2;



}
int main()
{
    string s;
    fin>>s;
    pal(s);fout<<sum;
    return 0;
}