Cod sursa(job #2736403)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 3 aprilie 2021 14:07:52
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 fin("pscpld.in");
ofstream fout("pscpld.out");
string s, t;
using ll = long long;
const int NMAX = 2e6;
int v[NMAX + 5];

int main()
{
    ll res = 0;
    fin >> s;
    t = "(*";
    for(char ch : s)
        t += ch,
        t += "*";
    t += ")";
    int n = t.length(), radius = 0, center = 0;
    for(int i = 1; i < n; i++) {
        int mirror = 2 * center - i;
        if(i < center + radius) v[i] = min(radius + center - i, v[mirror]);
        while(t[i + v[i] + 1] == t[i - v[i] - 1]) v[i]++;
        if(i + v[i] > center + radius)
            center = i,
            radius = v[i];
    }
    for(int i = 1; i < n; i++)
        res += (v[i] + 1) / 2;
    fout << res;
    return 0;
}