Cod sursa(job #2289978)

Utilizator akaprosAna Kapros akapros Data 25 noiembrie 2018 16:37:41
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
#define ll long long
#define maxN 100000
using namespace std;

FILE *fin = freopen("pscpld.in", "r", stdin);
FILE *fout = freopen("pscpld.out", "w", stdout);

char s[maxN + 1];
class String
{
public :
    int n, *p;
    char *Q;
    String(int n)
    {
        this->n = n;
        p = new int[2 * n + 2];
        Q = new char[2 * n + 2];
        Q[2 * n + 1] = '$';
        for (int i = 0; i <= 2 * n + 1; ++ i)
            p[i] = 0;
        for (int i = 0; i <= 2 * n; ++ i)
            if (i & 1)
                Q[i] = s[i / 2];
            else
                Q[i] = '#';
    }
    void compP();
};

ll ans;

void String::compP()
{
    int N = 2 * n + 1;
    int c = 0, r = 0;
    for (int i = 1; i < N; ++ i)
    {
        int iMirror = 2 * c - i;
        if (r > i)
            p[i] = min(p[iMirror], r - i);
        while (i - p[i] - 1 >= 0 && Q[i + p[i] + 1] == Q[i - p[i] - 1])
            ++ p[i];
        if (p[i] + i > r)
        {
            c = i;
            r = i + p[i];
        }
        ans += ((p[i] + 1) / 2);
    }
}
int main()
{
    scanf("%s", &s);
    int n = strlen(s);
    String S(n);
    S.compP();
    printf("%lld\n", ans);
    return 0;
}