Cod sursa(job #2798424)

Utilizator stefanlupoi1Lupoi Stefan stefanlupoi1 Data 11 noiembrie 2021 11:50:53
Problema PScPld Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");

const int N = 2e6 + 5;

int v[N];
string s1, s2;

int main()
{
    long long result = 0;
    in >> s1;
    s2 = "(*";
    for(char c:s1){
        s2 += c;
        s2 += "*";
    }
    s2 += ")";
    int n = s2.size(), radius = 0, center = 0;
    for(int i = 1; i < n; i++){
        int opposite = 2 * center - i, p = center + radius;
        if(i < p) v[i] = min(p - i, v[opposite]);
        while(s2[i + v[i] + 1] == s2[i - v[i] - 1]) v[i]++;
        if(i + v[i] > p)
            center = i;
        radius = v[i];
    }
    for(int i = 1; i < n; i++){
        result += (v[i] + 1) >> 1;
    }
    out << result;
    return 0;
}