Cod sursa(job #3364282)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 1 septembrie 2026 11:24:55
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
#include <string>

#include <vector>

using namespace std;

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

const int nmax = 1e6;
int n, pal[2 * nmax + 2]; string ss, tt;

int main(){
    in>>ss; 

    tt = '$#';
    for(int i = 0; i < ss.size(); i++){
        tt += ss[i]; tt += '#';
    }
    tt += '&'; /// bounded with different characters

    /// manacher's algorithm ///
    for(int i = 1; i < tt.size() - 1; i++){
        for(; tt[i - pal[i]] == tt[i + pal[i]]; pal[i]++);
    }

    int64_t ways = 0;
    for(int i = 1; i < tt.size() - 1; i++){
        ways += (pal[i] / 2);
    }
    out<<ways<<"\n";

    return 0;
}