Cod sursa(job #2737908)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 5 aprilie 2021 12:02:50
Problema PScPld Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX(2000005);
char sir[NMAX], sir2[NMAX];
int pal[NMAX];

int main()
{
    fin.getline(sir + 1, NMAX - 3);
    int lg = strlen(sir + 1);
    int n = 0;
    sir2[++n] = '#';
    for(int i = 1; i <= lg; ++i)
        sir2[++n] = sir[i], sir2[++n] = '#';

    pal[1] = 1;
    int c = 1, dr = 1;
    long long rez = 0;
    for(int i = 2; i <= n; ++i){
        int lg = 0;
        if(i <= dr)
            lg = min(pal[2 * c - 1], dr - i + 1);
        while(i - lg > 0 && i + lg <= n && sir2[i + lg] == sir2[i - lg])
            ++lg;

        if(i + lg - 1 > dr){
            dr = i + lg - 1;
            c = i;
        }

        pal[i] = lg;
        if(i % 2 == 0)
            rez += (lg + 1) / 2;
        else rez += lg / 2;
    }

    fout << rez << '\n';
    return 0;
}