Cod sursa(job #2452104)

Utilizator StanCatalinStanCatalin StanCatalin Data 29 august 2019 16:22:31
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int dim = 2000005;

int len[dim],n,aux;
long long int ans = 0;

char s[dim],v[dim];

void Algoritm()
{
    int c = 0,r = 0;
    for (int i=1; i<2*n+1; i++)
    {
        if (i < r)
        {
            len[i] = min(r-i , len[2*c-i]);
        }

        while (v[i-len[i]-1] == v[i+len[i]+1])
        {
            len[i]++;
        }

        ans += (long long int)((len[i] + 1)/2);

        if (i + len[i] > r)
        {
            r = i+len[i];
            c = i;
        }
    }
}

int main()
{
    in >> (s+1);
    n = strlen(s+1);
    v[0] = '$';
    for(int i=1; i<=n; i++)
    {
        v[++aux] = '$';
        v[++aux] = s[i];
    }
    v[++aux] = '$';
    Algoritm();
    out << ans-1;
    return 0;
}