Cod sursa(job #2864932)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 8 martie 2022 12:33:29
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
/*
                         __
                   _.--""  |
    .----.     _.-'   |/\| |.--.
    |    |__.-'   _________|  |_)  _______________
    |  .-""-.""""" ___,    `----'"))   __   .-""-.""""--._
    '-' ,--. `    |Cezar| .---.       |:.| ' ,--. `      _`.
     ( (    ) ) __|  7  |__\\|// _..-- \/ ( (    ) )--._".-.
      . `--' ;\__________________..--------. `--' ;--------'
       `-..-'                               `-..-'
*/
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

const int N = 1e6 + 5;

char s[2*N];
int dp[2*N];

void addSpaces(ifstream &in){
    char s2[N];
    in>>s2;
    int  l = strlen(s2);
    for(int i = 0;i<l;i++){
        s[i*2] = '#';
        s[i*2+1] = s2[i];
    }
    s[l*2] = '#';
}

int main() {
    ifstream in("pscpld.in");
    ofstream out("pscpld.out");
    addSpaces(in);
    int l = strlen(s);
    int oglinda = 0,dr = 0;
    for(int i=0;i<l;i++){
    //    cout<<i<<' '<<oglinda<<' '<<dr<<'\n';
        if(i>=dr){
            while(i - dp[i]-1>=0 && i+dp[i]+1<l && s[i - dp[i]-1] == s[i+dp[i]+1]){
                dp[i]++;
            }
            oglinda = i;
            dr = i + dp[i] - 1;
        }
        else dp[i] = min(dp[oglinda - (i-oglinda)],dr-i+1);
    }
/*
    for(int i=0;i<l;i++) {
        out << s[i] << ' ';
    }
    out<<'\n';
*/
    int rez = 0;
    for(int i=0;i<l;i++) {
       // out << dp[i] << ' ';
        rez += dp[i]/2;
    }
    out<<rez + l/2;
    return 0;
}