Cod sursa(job #1605203)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 18 februarie 2016 20:31:40
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair

char s[2000010];
char ax[1000010];
int p[2000010];

int main(){
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    s[0] = '$';
    s[1] = '#';
    scanf("%s",ax+1);
    int n = strlen(ax+1);
    int l = 2;
    for(int i = 1;i <= n;i++){
        s[l++] = ax[i];
        s[l++] = '#';
    }
    s[l] = '@';
    int R,C;
    R = C = 0;
    ll sum = 0;
    for(int i = 1;i < l;i++){
        int mirr = 2*C-i;
        if(i < R){
            p[i] = min(R-i, p[mirr]);
        }
        while(s[i+1+p[i]] == s[i-1-p[i]]){
            p[i]++;
        }
        if(i+p[i] > R){
            R = i+p[i];
            C = i;
        }
        sum = sum+(p[i]+1)/2;
        //printf("%d ",p[i]);
    }
//    printf("\n");
//    for(int i = 1;i < l;i++){
//        printf("%c ",s[i]);
//    }
    printf("%lld",sum);
    return 0;
}