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