Cod sursa(job #2791266)

Utilizator teomarsTeodora Sintea teomars Data 30 octombrie 2021 12:06:57
Problema PScPld Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <cstdio>

using namespace std;

char s[1000005];
int n, p[1000005];

void citire(){
    char c;
    while(cin >> c){
        s[n++]='#';
        s[n++]=c;
    }
    s[n++]='#';
}

void lungimi(){
    int c = 0, r = 0, sim;
    for(int i = 0; i < n; i++){
        sim = c-(i-c);
        if(i <= r)
            p[i] = min(r-i, p[sim]);
        while(i+1+p[i] < n && i-1-p[i] >= 0 && s[i+1+p[i]] == s[i-1-p[i]])
            p[i]++;
        if(i+p[i]){
            c=i;
            r=i+p[i];
        }
    }
}

long long suma(){
    long long s = 0;
    for(int i = 0; i < n; i++)
        if(p[i])
            s = s+(p[i]+1)/2;
    return s;
}

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

    citire();
    lungimi();
    printf("%lld", suma());
    return 0;
}