Cod sursa(job #2761015)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 30 iunie 2021 08:04:49
Problema PScPld Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>
#define nmax (int)(2e6+2)
using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

string a,b;
int ps[nmax];

int main()
{
    f>>a;
    b.push_back('&');
    for(int i=0;i<a.size();i++)
    {
        b.push_back(a[i]);
        b.push_back('&');
    }

    int mid=-1,k=0;
    long long ans=0;

    for(int i=0;i<b.size();i++)
    {
        if(i<=k+mid)
            ps[i]=ps[2*mid-i];

        while(
              (i+ps[i]+1<b.size()&&i-ps[i]-1>=0)&&
              b[i+ps[i]+1]==b[i-ps[i]-1]) ps[i]++;

        if(ps[i]+i>mid+k)
        {
            mid=i;
            k=ps[i];
        }
       // g<<ps[i]<<' '<<i<<'\n';
        ans+=(long long)((ps[i]+i%2)/2);
    }
    g<<ans;
    return 0;
}