Cod sursa(job #2798385)

Utilizator stefanlupoi1Lupoi Stefan stefanlupoi1 Data 11 noiembrie 2021 11:32:42
Problema PScPld Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 2000005;

int v[N];
string s1, s2 = "(*";

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