Cod sursa(job #2335491)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 4 februarie 2019 10:40:15
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

char a[1000005];
char s[2000010];
int l,p;
int C, R, P[2000010], simi;

void add_hashes()
{
    l = strlen(a);
    for(int i=0; i<l; i++)
    {
        s[2*i] = '#';
        s[2*i+1] = a[i];
    }
    s[2*l] = '#';
    p = 2*l+1;
}

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

int main()
{
    f>>a;
    add_hashes();
    long long vmax=0;
    for(int i=1; i<p; i++)
    {
        simi = C-(i-C);
        if(i <= R)
            P[i] = min(R-i, P[simi]);
        while(i+1+P[i] < p && i-1-P[i] >= 0 && s[i+1+P[i]] == s[i-1-P[i]])
            {P[i]++;}
        if(i+P[i] > R)
        {
            C = i;
            R = i + P[i];
        }
        vmax += 1LL*(P[i]+1)/2;
    }
    g<<vmax;
    return 0;
}