Cod sursa(job #2289970)

Utilizator akaprosAna Kapros akapros Data 25 noiembrie 2018 16:30:47
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 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 + 1];
        Q = new char[2 * n + 1];
        Q[0] = '@';
        Q[2 * n] = '$';
        for (int i = 0; i <= 2 * n; ++ i)
            p[i] = 0;
        for (int i = 1; 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;
    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 (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] / 2);
    }
}
int main()
{
    scanf("%s", &s);
    int n = strlen(s);
    String S(n);
    S.compP();
    printf("%lld\n", ans + n);
    return 0;
}