Cod sursa(job #1975794)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 1 mai 2017 23:18:57
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

vector<int> pscpld(const string& str){
    const int n = str.size();
    vector<int> v(n, 0);
    for(int i = 0, mij = -1, dr = -1; i < n; ++i){
        for(v[i] = (dr <= i ? 0 : min(v[2*mij - i], dr-i));
            i+v[i]+1 < n && i-v[i]-1 >= 0 && str[i+v[i]+1] == str[i-v[i]-1];
            ++v[i]);
        if(i+v[i] > dr) mij = i, dr = i+v[i]; }
    return v; }

string intersperse(const string& str){
    string rez = "@";
    for(const auto x : str){
        rez.push_back(x);
        rez.push_back('@'); }
    return rez; }

int main(){
    ifstream f("pscpld.in");
    ofstream g("pscpld.out");
    string str;
    f >> str;
    str = intersperse(str);
    const auto pal_len = pscpld(str);
    
    g << accumulate(begin(pal_len), end(pal_len), 0ll,
        [](const long long x, const long long y){ return x + (y+1)/2ll; }) << endl;
    return 0; }