Cod sursa(job #3225529)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 17 aprilie 2024 19:52:03
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
long long n, i, r, l, st, dr, d[2000102];
string s = ".", c;

int main() {
    fin >> c;
    for(auto it : c) {
        s += it;
        s += ".";
    }

    n = s.size();
    for(i = 0; i < n; i++) {
        if(i <= dr) l = min(dr - i, d[st + dr - i]);
        else l = 1;

        while(0 <= i - l && i - l < n && s[i - l] == s[i + l]) l++;
        d[i] = l;

        if(l + i - 1 > dr) {
            st = i - l + 1;
            dr = i + l - 1;
        }
    }

    for(i = 0; i < n; i++) r += d[i] / 2;

    fout << r;

    return 0;
}