Cod sursa(job #2008802)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 7 august 2017 17:03:56
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>

using namespace std;

const int nMax = 2000005;

void Manacher(char v[], int sz, int ret[])
{
    ret[0] = 0;
    int st, dr;
    for(int i = 1; i < sz-1; ++i)
    {
        if(v[i-1] == v[i+1])
        {
            st = i - ret[i-1];
            dr = i + ret[i-1];
            ret[i] = ret[i-1] - 1;
            while(st >= 0 && dr < sz && v[st--] == v[dr++])
                ret[i]++;
        }
        else
            ret[i] = 0;
    }
    ret[sz-1] = 0;
}


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

int main()
{
   /* ifstream in("pscpld.in");
    in >> t;
    in.close();*/
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    fgets(t, sizeof(t), stdin);
    n = strlen(t) - 1;
    for(int i = 0; i < n; ++i)
        a[2 * i] = t[i], a[2 * i + 1] = '#';
    n = 2 * n - 1;
    Manacher(a, n, pal);
    long long rasp = 0;
    for(int i = 0; i < n; i += 2)
        rasp += (1LL * pal[i] / 2) + 1;
    for(int i = 1; i < n; i += 2)
        rasp += (1LL * pal[i] / 2);
    printf("%lld", rasp);
   /* ofstream out("pscpld.out");
    out << rasp;
    out.close();*/
    return 0;
}