Cod sursa(job #2284021)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 16 noiembrie 2018 16:26:05
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define pb push_back
#define MIN(a, b) (((a) > (b)) ? (b) : (a))

const int VM(1000000) ;

char ch[VM] ;
std::vector<char> v ;
std::vector<int> L(VM) ;

int GetPal() {
    register int i ;
    int 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 ;
        }
    }
    int ans(0) ;
    for (i = 0 ; i < L.size() ; ++ i) {
        ans += (L[i] - 1) / 2 ;
    }
    return ans ;
}

int main()
{
    freopen("pscpld.in", "r", stdin) ;
    freopen("pscpld.out", "w", stdout) ;
    register int i ;
    gets(ch) ;
    int n = strlen(ch) ;
    for (i = 0 ; i < n ; ++ i) {
        v.pb('|') ;
        v.pb(ch[i]) ;
    }
    v.pb('|') ;
    int answer = GetPal() + n ;
    printf("%d", answer) ;
    return 0;
}