Cod sursa(job #2016106)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 28 august 2017 16:55:28
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000005;
char a[NMAX * 2];
char v[NMAX];
int b[NMAX];

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    gets(a + 1);
    int m = strlen(a + 1), n = 0;
    for(int i = 1;i <= m; ++i) {
        v[++n] = a[i];
        v[++n] = '.';
    }
    v[0] = ' ';
    v[n] = '/';
    --n;
    int st = 0, dr = 0;
    for(int i = 1;i <= n; ++i) {
        if(i > dr) {
            b[i] = 1;
        }
        else {
            b[i] = min(dr - i + 1, b[dr + st - i]);
        }
        while(v[i - b[i]] == v[i + b[i]]) {
            ++b[i];
        }
        if(i + b[i] - 1 > dr) {
            st = i + 1 - b[i];
            dr = i + b[i] - 1;
        }
    }
    long long int s = 0;
    for(int i = 1;i <= n; ++i) {
        if(isalpha(v[i])) {
            s += ((b[i] + 1) / 2);
        }
        else {
            s += (b[i] / 2);
        }
    }
    printf("%lld\n", s);
    return 0;
}