Cod sursa(job #2385428)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 21 martie 2019 21:41:40
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n;
string s;
int L[2000002];
long long ans = 1;
int main()
{
    f >> s;
    n = s.size();
    int N = 2*n + 1;
    L[0] = 0;
    L[1] = 1;
    int C = 1, R = 2, i = 0, iMirror;
    int maxLPSLength = 0, maxLPSCenterPosition = 0;
    int diff = -1;
    for (int i = 2; i < N; i++)
    {
        iMirror  = 2*C-i;
        L[i] = 0;
        diff = R - i;
        if(diff > 0)
            L[i] = min(L[iMirror], diff);
        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]++;
        if (i + L[i] > R)
        {
            C = i;
            R = i + L[i];
        }
        ans += (L[i] / 2) + (L[i] % 2);
    }
    g << ans << '\n';
    return 0;
}