Cod sursa(job #2292205)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 29 noiembrie 2018 09:40:36
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;

const int nMax = 2000005;

void Manacher(char v[], int sz, int ret[])
{
    int R = -1, C = 0, rad;
    for(int i = 0; i < sz; ++i)
    {
        if(i <= R)
            rad = min(ret[2 * C - i], R - i) + 1;
        else
            rad = 0;
        while(i - rad >= 0 && i + rad < sz && v[i-rad] == v[i+rad])
            rad++;
        ret[i] = rad - 1;
        if(i + ret[i] - 1 > R)
        {
            C = i;
            R = i + ret[i] - 1;
        }
    }
}


int n;
char a[nMax];
char t[nMax];
int pal[nMax];

int main()
{
    ifstream in("pscpld.in");
    in >> t;
    in.close();
    n = strlen(t);
    for(int i = 0; i <= n; ++i)
        a[2 * i] = '#', a[2 * i + 1] = t[i];
    n = 2 * n + 1;
    Manacher(a, n, pal);
    long long rasp = 0;
    for(int i = 0; i < n; ++i)
        rasp += (1LL * (pal[i]+1) / 2);
    ofstream out("pscpld.out");
    out << rasp;
    out.close();
    return 0;
}