Cod sursa(job #3329601)

Utilizator vladneaguVladneagu vladneagu Data 14 decembrie 2025 14:02:38
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <math.h>
#include <queue>
#include <set>
#pragma GCC optimize ("Ofast","unroll-loops")
#pragma GCC target ("sse")
using namespace std;
#define int long long
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const int maxn=2e6+10;
int manacher[maxn];
void build_manacher(const string a) {
    int best=1;
    int n=a.size();
    for (int i=1;i<n;i++) {
        int simetric=best-(i-best);
        manacher[i]=min(manacher[simetric]+i,manacher[best]+best)-i;
        while (a[i+manacher[i]+1]==a[i-manacher[i]-1]) manacher[i]++;
        if (manacher[best]+best<manacher[i]+i)best=i;
    }
}
void solve(){
    string s1;
    cin>>s1;
    string s;
    s="##";
    for (auto elem:s1) {
        s.push_back(elem);
        s.push_back('#');
    }
    build_manacher(s);
    int rsp=0;
    for (int i=0;i<s.size();i++) {
        rsp+=(manacher[i]+1)/2;
    }
    cout<<rsp;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    while(t--)solve();
    return 0;
}