Cod sursa(job #1941768)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 27 martie 2017 16:19:07
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6+5;
int n, id, i, l[2*Nmax];
char b[Nmax], a[2*Nmax];
long long ans=0;

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);

    scanf("%s\n", b+1);
    n = strlen(b+1);

    for(i=1; i<=n; ++i)
        a[2*i-1] = '#', a[2*i] = b[i];
    a[n = 2*n+1] = '#';

    id = 0;
    for(i=1; i<=n; ++i)
    {
        if(id + l[id] > i) l[i] = l[2*id-i];
        else l[i] = 1;

        while(i > l[i] && a[i-l[i]] == a[i+l[i]]) ++l[i];

        ans += l[i] / 2;
        if(i + l[i] > id + l[id]) id = i;
    }

    printf("%lld\n", ans);

    return 0;
}