Cod sursa(job #1299033)

Utilizator cojocarugabiReality cojocarugabi Data 23 decembrie 2014 14:07:13
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
# include <bits/stdc++.h>
using namespace std;
const int nmax = 2e6 + 5;
int  s[nmax];
char v[nmax];
int main(void)
{
    ifstream fi("pscpld.in");
    ofstream fo("pscpld.out");
    fi>>(v + 1);
    int n = strlen(v + 1);
    for (int i=n-1;i + 1;--i) v[i * 2 + 1] = v[i + 1];n <<= 1;
    v[0] = '%';v[n + 1] = '#';s[1] = 1;
    for (int i=2;i<=n;++++i) v[i] = '^';
    int p=1,l=1;
    for (int i=1;i<=n;++i)
    {
        s[i]=min(p+l-i,s[p*2-i]);
        while (v[i - s[i]] == v[i + s[i]]) ++s[i];
        if (s[i] + i > p + l) p = i,l = s[i];
    }
    long long S=0;
    for (int i=1;i<=n;++i) S+=(s[i] + (i&1)) / 2;
    return fo << S << '\n',0;
}