Cod sursa(job #2315689)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 10 ianuarie 2019 14:00:47
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int V[1<<21];
string A, S;
int main()
{
    f>>A;
    S+="@";
    for(int i=0;i<(int)A.size();++i)
    {
        S+="+";
        S+=A[i];
    }
    S+="+@";
    int r=0,c=0;
    for(int i=1;i<(int)S.size()-1;++i)
    {
        if(i<r)
            V[i]=min(r-i,V[c*2-i]);
        while(i-V[i]-1>0&&
              i+V[i]+1<(int)S.size()&&
              S[i-V[i]-1]==S[i+V[i]+1]) V[i]++;
        if(r<V[i]+i)
        {
            r=V[i]+i;
            c=i;
        }
    }
    long long nr=0;
    for(int i=1;i<(int)S.size();++i)
        nr+=(V[i]+1)/2;
    g<<nr;
    return 0;
}