Cod sursa(job #2008800)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 7 august 2017 16:59:35
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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;
    char add[3];
    add[1] = '#';
    add[2] = '\0';
    for(int i = 0; i < n; ++i)
    {
        add[0] = t[i];
        strcat(a, add);
    }
    n = strlen(a) - 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;
}