Cod sursa(job #2475790)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 17 octombrie 2019 16:38:34
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;

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

long long man(string x)
{
    int l=0, r=-1;
    long long sum=0;
    int n=x.size();
    vector<int> d1(n), d2(n);
    for(int i=0;i<n;++i)
    {
        if(i<=r) d1[i]=min(r-i+1, d1[l+r-i]);
        else d1[i]=1;
        while(x[i+d1[i]]==x[i-d1[i]]&&i-d1[i]>=0&&i+d1[i]<n) d1[i]++;
        if(i+d1[i]>r)
        {
            r=i+d1[i]-1;
            l=i-d1[i]+1;
        }
        sum+=d1[i];
    }
    l=0, r=-1;
    for(int i=0;i<n;++i)
    {
        if(i<=r) d2[i]=min(r-i+1, d2[l+r-i+1]);
        else d2[i]=0;
        while(x[i+d2[i]]==x[i-d2[i]-1]&&i-d2[i]-1>=0&&i+d2[i]<n) d2[i]++;
        if(i+d2[i]>r)
        {
            r=i+d2[i]-1;
            l=i-d2[i];
        }
        sum+=d2[i];
    }
    return sum;
}

int main()
{
    string x;
    fin>>x;
    fout<<man(x)<<"\n";
    return 0;
}