Cod sursa(job #2866192)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 9 martie 2022 13:47:26
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s;
int n;
void Manacher()
{
    if (n == 0){
        fout << 0 << '\n';
        return;
    }
    int N = 2 * n + 1;
    int L[N];
    L[0] = 0;
    L[1] = 1;
    // C = centerPosition, R = centerRightPosition, i = currentRightPosition
    // iMirror = currentLeftPosition
    int C = 1, R = 2, iMirror, 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])>0 && ( ((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];
        }

    }

    long long ans = 0;
    for (int i=0;i<N;i++){
        ans += (L[i] + 1) / 2;
    }
    fout << ans << '\n';

}

int main() {
    getline(fin, s);
    n = s.size();

    Manacher();
    return 0;
}