Cod sursa(job #636914)

Utilizator Teodor94Teodor Plop Teodor94 Data 20 noiembrie 2011 01:46:01
Problema PalM Scor 20
Compilator cpp Status done
Runda .com 2011 Marime 1.59 kb
#include<cstdio>
#include<cstring>

const int N = 505;

int n, st[N], dr[N];
char s[N];

inline int min(int x, int y) {
    return x < y ? x : y;
}

bool alfa(int x, int y, int tip) {
    for (int i = x; i < y; ++i)
        if (tip == 1) {
            if (s[i] > s[i+1])
                return false;
        }
        else {
            if (s[i] < s[i+1])
                return false;
        }
    return true;
}

int cautbin(int x, int tip) {
    int i, pas = (1 << 9);

    for (i = 0; pas; pas >>= 1)
        if (tip == 1) {
            if (x - i - pas >= 0 && alfa(x - i - pas, x, 1))
                i += pas;
        }
        else {
            if (x + i + pas < n && alfa(x, x + i + pas, 2))
                i += pas;
        }

    if (tip == 1)
        return x - i;

    return x + i;
}

void munte() {
    for (int i = 0; i < n; ++i) {
        st[i] = cautbin(i, 1);
        dr[i] = cautbin(i, 2);
    }
}

bool palind(int x, int y) {
    while (s[x] == s[y] && x < y) {
        ++x;
        --y;
    }

    if (x >= y)
        return true;

    return false;
}

void rez() {
    int lgmax = 0;


    for (int i = 0; i < n; ++i)
        for (int j1 = st[i]; j1 <= i; ++j1)
            for (int j2 = dr[i]; j2 >= i; --j2)
                if (j2 - j1 + 1 <= lgmax)
                    break;
                else
                if (palind(j1, j2) && j2 - j1 + 1 > lgmax)
                        lgmax = j2 - j1 + 1;

    printf("%d\n", lgmax);
}

int main() {
    freopen("palm.in", "r", stdin);
    freopen("palm.out", "w", stdout);

    gets(s);
    n = strlen(s);

    munte();

    rez();

    return 0;
}