Cod sursa(job #3170042)

Utilizator gizzehhhAsavoaei Bianca Gabriela gizzehhh Data 16 noiembrie 2023 18:19:07
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define N 1000005

using namespace std;

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

char s[N], c[2*N];
int dims, dimc = -1, st, dr;
int dist[2*N];
long long result;

///Manacher's algorithm - used to find the longest palindromic substring in any string

int main() {

    fin >> s; /// abaaac
    dims = strlen(s);
    dimc ++;
    c[dimc] = '!';
    dimc ++;
    c[dimc] = '*'; /// *a*b*a*a*a*c
    for(int i = 0; i < dims; i++)
    {
        dimc ++;
        c[dimc] = s[i];

        dimc++;
        c[dimc] = '*';

    }
    dimc++;
    c[dimc] = '?';
    dimc++;
    c[dimc] = 0;
    st = -1;
    dr = -1;
    for(int i = 0; i < dimc; i++)
    {
        if(i > dr) dist[i] = 0;
        else
            dist[i] = min(dr - i, dist[st+dr-i]);

        while(c[dist[i]+i] == c[i - dist[i]])
            dist[i] ++;
        dist[i] --;

        if(i+dist[i] > dr)
        {
            st = i - dist[i];
            dr = i + dist[i];
        }
    }

    for(int i = 0; i < dimc; i ++)
        result += (dist[i] + 1)/2;


    fout << result;

    return 0;
}