Cod sursa(job #636876)

Utilizator Teodor94Teodor Plop Teodor94 Data 20 noiembrie 2011 00:50:22
Problema PalM Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 1.44 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) {
        int m = min(i - st[i], dr[i] - i);

        if (palind(i - m, i + m) && lgmax < 2 * m+ 1)
            lgmax = 2 * m + 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;
}