Cod sursa(job #2442528)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 24 iulie 2019 11:56:19
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
char c[2000005];
int mx[2000005];
int main()
{
    ifstream cin("pscpld.in");
    ofstream cout("pscpld.out");
    int n,dr=0,st=0;
    string s;
    cin>>s;
    n=s.size();
    for(int i=0;i<n;i++)
    {
        c[2*i+1]=s[i];
        c[2*(i+1)]='*';
    }
    c[0]='*';
    n*=2;
    for(int i=1;i<=2*n;i++)
    {
        if(i<=dr)
        {
            int o=st+dr-i;
            mx[i]=min(mx[o],o-st+1);
            int jdr=i+mx[i],jst=i-mx[i];
            while(jst>=0 and jdr<=n and c[jdr]==c[jst])
            {
                jdr++;
                jst--;
                mx[i]++;
            }
            if(dr<i+mx[i]-1)
            {
                dr=i+mx[i]-1;
                st=i-mx[i]+1;
            }
        }
        else
        {
            int jdr=i,jst=i;
            while(jst>=0 and jdr<=n and c[jdr]==c[jst])
            {
                jdr++;
                jst--;
                mx[i]++;
            }
            dr=i+mx[i]-1;
            st=i-mx[i]+1;
        }
    }
    long long sum=0;
    for(int i=1;i<=n;i++)
        sum+=(long long)mx[i]/2;
    cout<<sum;
    return 0;
}