Cod sursa(job #1876485)

Utilizator Burbon13Burbon13 Burbon13 Data 12 februarie 2017 13:40:36
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int nmx = 1000002;

char s1[nmx],s2[2*nmx];
int l[2*nmx];
long long suma;

void citire()
{
    scanf("%s", s1);

    int x = strlen(s1), p = 1;

    s2[0] = '#';

    for(int i = 0; i < x; ++i)
    {
        s2[p++] = s1[i];
        s2[p++] = '#';
    }

    s2[p] = NULL;
}

void manacher()
{
    int c = 0, r = 0, st, dr, x = strlen(s2);
    for(int i = 1; i < x; ++i)
    {
        if(i > r)
        {
            st = i - 1;
            dr = i + 1;
            if(s2[i] != '#')
                l[i] = 1;
        }
        else
        {
            int ii = 2 * c - i;
            l[i] = min(r-i,l[ii]);
            st = i - l[ii];
            dr = i + l[ii];
        }

        while(st >= 0 && s2[st] == s2[dr])
        {
            if(s2[st] != '#')
                l[i] += 2;
            -- st;
            ++ dr;
        }

        if(i + l[i] > r)
        {
            r = i + l[i];
            c = i;
        }

        suma += (l[i] + 1) / 2;
    }
}

void afish()
{
    /**for(int i = 0; i < strlen(s2); ++i)
        printf("%c ", s2[i]);
    printf("\n");
    for(int i = 0; i < strlen(s2); ++i)
        printf("%d ", l[i]);**/
    printf("%d\n", suma);
}

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    citire();
    manacher();
    afish();
    return 0;
}