Nu aveti permisiuni pentru a descarca fisierul grader_test2.ok

Cod sursa(job #989141)

Utilizator gbi250Gabriela Moldovan gbi250 Data 24 august 2013 23:10:48
Problema PalM Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char s[512], aux[512];
int i, l, r, p[1024], n, MAX, pz;

inline void expand(int &l, int &r)
{
    while(s[l-1]==s[r+1] && l>=2 && r<=n-1)
        ++p[i], ++r, --l;
}

inline void manacher()
{
    int len=strlen(aux)-1;
    for(i=0;i<=len;++i)
    {
        s[++n]=aux[i];
        s[++n]='#';
    }
    for(i=2;i<=n;++i)
    {
        if(i<=r)
        {
            p[i]=min(p[r-i+l], r-i);
            if(p[i]==r-i)
            {
                l=i-p[i];
                expand(l, r);
            }
        }
        else
        {
            r=l=i;
            expand(l, r);
        }
        if(p[i]>MAX)
        {
            MAX=p[i];
            pz=i;
        }
    }
}

int main()
{
    freopen("palm.in", "r", stdin);
    freopen("palm.out", "w", stdout);
    scanf("%s", aux);
    manacher();
    for(i=pz;i<=n && i-pz<=MAX;i+=2)
        if(s[i]<s[i+2])
            MAX--;
    printf("%d\n", MAX);
    return 0;
}