Cod sursa(job #1513761)

Utilizator akaprosAna Kapros akapros Data 29 octombrie 2015 22:18:48
Problema PScPld Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1000002
using namespace std;
int n, i, j, pos, a;
long long sol, len[maxN * 2];
char s[maxN * 2], S[maxN];
void read()
{
    freopen("pscpld.in", "r", stdin);
    gets(S + 1);
    n = strlen(S + 1);
    s[0] = '*';
    for (i = 1; i <= 2 * n; ++ i)
    {
        if (i % 2)
        s[i] = S[(i + 1) / 2];
        else
            s[i] = '*';
    }
    n *= 2;
}
void solve()
{
    pos = 0;
    a = 0;
    sol = 0;
    for (i = 1; i <= n; ++ i)
    {
        if (i <= pos)
            len[i] = min(len[2 * a - i], (pos - i) * 1LL);
        while (i - len[i] - 1 >= 0 && i + len[i] + 1 <= n && s[i - len[i] - 1] == s[i + len[i] + 1])
            ++ len[i];
        if (i + len[i] > pos)
        {
            pos = i + len[i];
            a = i;
        }
        sol = sol + (len[i] + 1) / 2;
    }
}
void write()
{
    freopen("pscpld.out", "w", stdout);
    printf("%lld\n", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}