Cod sursa(job #2005986)

Utilizator giotoPopescu Ioan gioto Data 28 iulie 2017 15:41:37
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;

char s[1000005], T[2000005];
int P[2000005];
int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    fgets(s, sizeof(s), stdin);
    int L = strlen(s) - 1;
    for(int i = 0; i <= L ; ++i)
        T[2 * i] = '#', T[2 * i + 1] = s[i];
    int n = strlen(T), C = 0, R = -1, rad, Sol = 0;
    for(int i = 0; i < n ; ++i){
        if(i <= R) rad = min(P[2 * C - i], R - i) + 1;
        else rad = 0;
        while(i + rad < n && i - rad >= 0 && T[i - rad] == T[i + rad]) ++rad;
        P[i] = rad - 1;
        if(i + rad - 1 > R){
            C = i;
            R = i + rad - 1;
        }
        Sol = Sol + (P[i] + 1) / 2;
    }
    printf("%d", Sol);
    return 0;
}