Cod sursa(job #2284078)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 16 noiembrie 2018 19:07:10
Problema PScPld Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#define pb push_back
#define MIN(a, b) (((a) > (b)) ? (b) : (a))

const int VM(2000005) ;

std::string ch ;
std::vector<char> v ;
long long L[VM] ;

long long GetPal() {
    register long long i ;
    long long left(0), right(0), pos(0) ;
    for (i = 0 ; i < v.size() ; ++ i) {
        if(i > right)
            pos = 0 ;
        else
            pos = MIN(L[right + left - i], right - i) ;
        while (i + pos < v.size() && i - pos >= 0 && v[i - pos] == v[i + pos])
            ++ pos ;
        L[i] = pos -- ;
        if (i + pos > right) {
            right = i + pos ;
            left = i - pos ;
        }
    }
    long long ans(0) ;
    for (i = 0 ; i < v.size() ; ++ i) {
        ans += (L[i] - 1) / 2 ;
    }
    return ans ;
}

int main()
{
    freopen("pscpld.in", "r", stdin) ;
    freopen("pscpld.out", "w", stdout) ;
    register long long i ;
    std::cin >> ch ;
    long long n = ch.size() ;
    for (i = 0 ; i < n ; ++ i) {
        v.pb('*') ;
        v.pb(ch[i]) ;
    }
    v.pb('*') ;
    long long answer = GetPal() + n ;
    printf("%lld", answer) ;
    return 0;
}