Cod sursa(job #1940360)

Utilizator cristina_borzaCristina Borza cristina_borza Data 26 martie 2017 16:10:56
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 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] = aux[i];
        cuv[2 * i - 1] = '$';
    }

    cuv[2 * n] = '$';

    n = 2 * n;
    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;
        //g << ans[i] << " ";
    }

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