ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1297. Palindrome

Got a WA on #27
Posted by Kenith Chu 21 Feb 2019 15:54
my cpp code is following:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int N = 5010, INF = 0x3f3f3f3f;

int c[N], sa[N], x[N], y[N];

void GetSA(int *r, int *sa, int n, int m)
{
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[x[i] = r[i]]++;
    for (int i = 2; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i >= 1; i--) if (c[x[i]]) sa[c[x[i]]--] = i;
    for (int k = 1, p = 0; k <= n; k <<= 1, p = 0)
    {
        for (int i = n - k + 1; i <= n; i++) y[++p] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
        for (int i = 1; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[x[i]]++;
        for (int i = 2; i <= m; i++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y); x[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
        if (p == n) break; m = p;
    }
}

int hei[N], rnk[N];

void GetH(int *r, int *sa, int n)
{
    for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
    for (int i = 1, k = 0, j; i <= n; hei[rnk[i++]] = k)
        for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++);
}

int n;

int s[N];
char str[N];

bool check(int a, int b, int len)
{
    return n - a + 2 == b + len;
}

int main()
{
    int mx = 0;
    scanf("%s", str + 1);
    int len = strlen(str + 1);
    for (int i = 1; i <= len; i++) s[i] = str[i], mx = max(mx, s[i]);
    s[len + 1] = '$';
    for (int i = len; i >= 1; i--) s[len * 2 - i + 2] = str[i];
    n = (len << 1) + 1;
    GetSA(s, sa, n, 1000);
    GetH(s, sa, n);
    P ans = P(1, -1);
    for (int i = 3; i <= n; i++)
    {
        int a = max(sa[i - 1], sa[i]), b = min(sa[i - 1], sa[i]);
        if (!(a > len + 1 && b <= len)) continue;
        if (check(a, b, hei[i]) && P(hei[i], -b) > ans) ans = P(hei[i], -b);
    }
    int pos = -ans.se;
    for (int i = pos; i < pos + ans.fi; i++) printf("%c", str[i]); puts("");
    return 0;
}

I've tried to enlarge the alphabet size, but there's no effect.

I also test lots of random test cases, all of them are correct.

I hope someone could give me a hack data.

Edited by author 21.02.2019 15:57
Re: Got a WA on #27
Posted by PixSor 21 Feb 2019 16:57
All right, I knew what's wrong...
Re: Got a WA on #27
Posted by GJC_xj 3 May 2019 11:57
can you tell me why you wrong? i wrong on #27 too