Cod sursa(job #2008722)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 7 august 2017 14:52:46
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int nMax = 1000005;

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();
    n = strlen(t);
    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);
    int rasp = 0;
    for(int i = 0; i < n; i += 2)
        rasp += (pal[i] / 2) + 1;
    for(int i = 1; i < n; i += 2)
        rasp += (pal[i] / 2);
    ofstream out("pscpld.out");
    out << rasp;
    out.close();
    return 0;
}