Cod sursa(job #1242272)

Utilizator smaraldaSmaranda Dinu smaralda Data 14 octombrie 2014 10:48:27
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#include<string.h>

const int NMAX = 1e6 + 5;

#define LL long long

char s[NMAX * 3], aux[NMAX];
int d[NMAX * 3];

int main() {
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    int i, right, pos, len;
    LL cnt;

    scanf("%s", aux + 1);
    len = strlen(aux + 1);
    for(i = 1; i <= len; ++ i) {
        s[2 * i - 1] = '$';
        s[2 * i] = aux[i];
    }
    s[2 * len + 1] = '$';
    s[0] = '#';

    len = 2 * len + 1;
    right = 0;
    for(i = 1; s[i] != NULL; ++ i) {
        if(i >= right) {
            right = pos = i;
            while(right <= len && s[right] == s[pos - (right - pos)])
                ++ right;
            -- right;
            d[i] = right - i;
            continue;
        }

        if(d[pos - (i - pos)] + i >= right) {
            pos = i;
            while(right <= len && s[right] == s[pos - (right - pos)])
                ++ right;
            -- right;
            d[i] = right - i;
            continue;
        }

        d[i] = d[pos - (i - pos)];
    }
    
    cnt = 0;
    for(i = 1; i <= len; ++ i)
        cnt += ((LL)d[i] + 1) / 2;
    printf("%lld\n", cnt);
    return 0;
}