Cod sursa(job #1099069)

Utilizator Ionut228Ionut Calofir Ionut228 Data 5 februarie 2014 15:28:21
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

char s[2000010];
int N;
long long sol;
int P[2000010];

void pscpld()
{
    int best = 0;

    for (int i = 1; i <= N; ++i)
    {
        if (best + P[best] >= i)
            P[i] = min(best + P[best] - i, P[2 * best - i]);
        while (i - P[i] - 1 > 0 && i + P[i] + 1 <= N && s[i - P[i] - 1] == s[i + P[i] + 1])
            ++P[i];
        if (i + P[i] >= best + P[best])
            best = i;
    }
}

int main()
{
    fin.getline(s + 1, 1000001);
    N = strlen(s + 1);

    for (int i = 2 * N + 1; i > 0; --i)
    {
        if (i % 2 == 1)
            s[i] = ' ';
        else
            s[i] = s[i / 2];
    }
    N = 2 * N + 1;

    pscpld();

    for (int i = 2; i <= N - 1; ++i)
    {
        if ((i - 1) % 2 == 1)
            sol += (P[i] + 1) / 2;
        else
            sol += P[i] / 2;
    }

    fout << sol << '\n';

    fin.close();
    fout.close();
    return 0;
}