Cod sursa(job #3364287)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 1 septembrie 2026 11:35:56
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 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, st = 0, dr = -1; i < tt.size() - 1; i++){
        if(i <= dr) pal[i] = max(0, min(pal[st + dr - i], dr - i + 1));
        
        for(; tt[i - pal[i]] == tt[i + pal[i]]; pal[i]++);
   
        if(i + pal[i] - 1 > dr){
            st = i - pal[i] + 1;
            dr = i + pal[i] - 1;
        }
    }

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

    return 0;
}