Cod sursa(job #3245379)

Utilizator serbanbBrindescu Serban serbanb Data 28 septembrie 2024 18:46:05
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>

using namespace std;

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

string s,s2;
int v[2000005];

int main()
{
    fin >> s;
    s2+='$';
    for(int i=0;i<s.size();++i){
        s2+='#';
        s2+=s[i];
    }
    s2+='#';
    s2+='@';
    int sz=s2.size();
    int center=0,right=0,mirror;
    for(int i=1;i<sz;++i){
        if(i<right){
            mirror=2*center-i;
            v[i]=min(v[mirror],right-i);
        }
        while(s2[i+1+v[i]]==s2[i-1-v[i]]){
            v[i]++;
        }
        if(i+v[i]>right){
            center=i;
            right=i+v[i];
        }
    }
    long long cnt=0;
    for(int i=0;i<sz;++i){
        if(v[i]>0){
            cnt+=1LL*((v[i]-1)/2+1);
        }
    }
    fout << cnt;
    return 0;
}