Cod sursa(job #2385455)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 21 martie 2019 21:55:36
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string s;
long long ans = 1;
int L[2000002], n, centru = 1, centruR = 2, dr, st, N;
int main()
{
    f >> s;
    n = s.size();
    N = 2*n + 1;
    L[1] = 1;
    int mx = 0;
    for (int i = 2; i < N; i++)
    {
        int st = 2 * centru - i;
        if(centruR > i)
            L[i] = min(L[st], centruR - i);
        while (((i + L[i]) < N && i > L[i]) && ( ((i + L[i] + 1) % 2 == 0) || (s[(i + L[i] + 1)/2] == s[(i - L[i] - 1)/2])))
            L[i]++;
        ans += L[i] / 2 + (L[i] & 1);
        if (i + L[i] > centruR)
        {
            centru = i;
            centruR = i + L[i];
        }
    }
    g << ans << '\n';
    return 0;
}