Cod sursa(job #2335044)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 3 februarie 2019 15:52:24
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
/** Cel mai lung subsir palindrom**/
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

char s[200010];
int l;
int P[200010]; /// p[i] retine lungimea palindroamelor centrate pe i
int C, R, simi;

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

void add_hashes()
{
    char t[100010];
    f.getline(t, 100010);
    int p = strlen(t);
    for(int i=0; i<2*p; i++)
    {
        s[2*i] = '#';
        s[2*i+1] = t[i];
    }
    s[2*p] = '#';
    l = 2*p+1;

}


int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    add_hashes(); /// se adauga elemente care nu se gasesc (pt subsiruri de lungime para);
    C = 0;
    R = 0;
    int vm=0;
    for(int i=1; i<l; i++)
    {
        simi = C-(i-C);
        P[i] = 0;
        if(R > i){
            P[i] = min(R-i, P[simi]); /// intr-un fel, maximul pe care il poate sustine
        }
        while(s[i+1+P[i]] == s[i-1-P[i]] && i-1-P[i] >= 0 && i + 1 + P[i] <l)
        {
            P[i]++;
        }
        if(i + P[i] > R)
        {
            C = i;
            R = i + P[i];
        }
        vm = vm + (P[i]+1)/2;
    }
    g<<vm;
    return 0;
}