Cod sursa(job #2335028)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 3 februarie 2019 15:08:43
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
/** Cel mai lung subsir palindrom**/
#include <cstdio>
#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;


void add_hashes()
{
    char c;
    while(scanf("%c", &c) != EOF && c != '\n')
    {
        s[l++] = '#';
        s[l++] = c;
    }
    s[l++] = '#';

}


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];
        }
    }
    for(int i=0; i<l; i++)
        if(P[i] != 0)
            vm = vm + (P[i]+1)/2;
    printf("%d", vm);
    return 0;
}