Cod sursa(job #2864981)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 8 martie 2022 13:02:44
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 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=1;i<l;i++){
     //   cout<<i<<' '<<oglinda<<' '<<dr<<'\n';
        if(i<=dr)
            dp[i] = min(dp[oglinda - (i - oglinda)], dr - i+1);
        while(i - dp[i]-1>=0 && i+dp[i]+1<l && s[i - dp[i]-1] == s[i+dp[i]+1]){
            dp[i]++;
        }
        if(i+dp[i]>=dr) {
            oglinda = i;
            dr = i + dp[i]+1;
        }

    }
/*
    for(int i=0;i<l;i++)
        out<<i<<' ';
    out<<'\n';

    for(int i=0;i<l;i++) {
        out << s[i] << ' ';
        if(i>9)
            out<<' ';
    }
    out<<'\n';
*/
    int rez = 0;
    for(int i=0;i<l;i++) {
      //  out << dp[i] << ' ';
     //   if(i>9)
         //   out<<' ';
        rez += (dp[i]+1)/2;
    }
    out<<rez;
    return 0;
}