Cod sursa(job #1940339)

Utilizator cristina_borzaCristina Borza cristina_borza Data 26 martie 2017 16:02:51
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f ("pscpld.in");
ofstream g ("pscpld.out");

const int Dim = 2000005;

long long n, pos, lg, sol;
long long ans[Dim];

char cuv[Dim], aux[Dim];

int main() {
    f >> (aux + 1);
    n = strlen (aux + 1);

    for (int i = 1; i <= n; ++i) {
        cuv[2 * i - 1] = aux[i];
        cuv[2 * i] = '$';
    }

    n = 2 * n - 1;
    pos = -1, lg = 0;

    for (int i = 1; i <= n; ++i) {
        if (pos + lg < i) {
            pos = i;
            lg = 0;

            while (pos + lg <= n && pos - lg >= 1 && cuv[pos + lg] == cuv[pos - lg]) {
                ++lg;
            }

            --lg;
            ans[i] = lg;
        }

        else {
            int p = 2 * pos - i;
            if ( ans [p] + i > pos + lg )
                ans [i] = pos + lg - i;

            else {
                if (ans [p] + i < pos + lg)
                    ans [i] = ans[p];

                else {
                    lg = ans[p];
                    while (i + lg <= n && i - lg >= 1 && cuv[i - lg] == cuv[i + lg])
                        ++lg;

                    --lg;
                    ans [i] = lg;
                    pos = i;
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        sol += ans[i] / 2;
    }

    sol += (n + 1) / 2;
    g << sol;
    return 0;
}