Cod sursa(job #2960223)

Utilizator divadddDavid Curca divaddd Data 3 ianuarie 2023 19:26:53
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#define MAX 2000052
#define int long long
using namespace std;
string s;
int p[MAX],l,r,n;

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

signed main()
{
    fin >> s;
    string aux = "$";
    for(auto ch: s){
        aux += "#";
        aux += ch;
    }
    aux += "#^";
    s = aux;
    l = r = 1;
    n = s.size() - 2;
    for(int i = 1; i <= n; i++){
        if(r > i){
            p[i] = min(r-i, p[l+(r-i)]);
        }else{
            p[i] = 0;
        }
        while(s[i+p[i]] == s[i-p[i]]){
            p[i]++;
        }
        if(i+p[i] > r){
            r = i+p[i];
            l = i-p[i];
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans += p[i]/2;
    }
    fout << ans;
    return 0;
}