【URAL 1297】Palindrome 最长回文子串

时间：2024-05-22 10:35:50

模板题，，，模板打错查了1h+QAQ

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1000003;

int t1[N], t2[N], c[N], f[N][30];

void st(int *x, int *y, int *sa, int n, int m) {

	int i;

	for(i = 0; i < m; ++i) c[i] = 0;

	for(i = 0; i < n; ++i) ++c[x[y[i]]];

	for(i = 1; i < m; ++i) c[i] += c[i - 1];

	for(i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];

}

void mkhz(int *a, int *sa, int n, int m) {

	int *t, *x = t1, *y = t2, i, j, p;

	for(i = 0; i < n; ++i) x[i] = a[i], y[i] = i;

	st(x, y, sa, n, m);

	for(j = 1, p = 1; p < n; j <<= 1, m = p) {

		for(p = 0, i = n - j; i < n; ++i) y[p++] = i;

		for(i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

		st(x, y, sa, n, m);

//		for(i = 1; i < n; ++i) printf("%d ", sa[i]); puts("");

		for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, p = 1, i = 1; i < n; ++i)

			x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j] ? p - 1 : p++;

		}

}

void mkh(int *r, int *sa, int *rank, int *h, int n) {

	int k = 0, i, j;

	for(i = 1; i <= n; ++i) rank[sa[i]] = i;

	for(i = 1; i <= n; h[rank[i++]] = k)

		for(k ? k-- : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; ++k);

}

void mkst(int *h, int n) {

	int k = floor(log((double)n) / log(2.0));

	for(int i = 1; i <= n; ++i)

		f[i][0] = h[i];

	for(int j = 1; j <= k; ++j)

		for(int i = 1; i <= n; ++i) {

			if (i + (1 << j) - 1 > n) break;

			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

		}

}

char s[N];

int n, sa[N], a[N], rank[N], h[N];

int rmq(int l, int r) {

	l = rank[l]; r = rank[r];

	if (l > r) swap(l, r); ++l;

	int k = floor(log((double)(r - l + 1)) / log(2.0));

	return min(f[l][k], f[r - (1 << k) + 1][k]);

}

int main() {

	while (scanf("%s", s + 1) != EOF) {

		n = strlen(s + 1);

		for(int i = 1; i <= n; ++i) a[i] = s[i];

		a[n + 1] = 126;

		for(int i = 1; i <= n; ++i)

			a[n + 1 + i] = a[n + 1 - i];

		mkhz(a, sa, n * 2 + 2, 130);

		mkh(a, sa, rank, h, n * 2 + 1);

		mkst(h, n * 2 + 1);

//		for(int i = 1; i <= n * 2 + 1; ++i) printf("%d ", sa[i]); puts("");

//		for(int i = 1; i <= n * 2 + 1; ++i) printf("%d ", rank[i]); puts("");

		int ans = 0, x, h, t;

		for(int i = 1; i <= n; ++i) {

//			ans = max(ans, rmq(i, 2 * n + 2 - i) * 2 - 1);

//			if (i != 1 && a[i - 1] == a[i]) ans = max(ans, rmq(i, 2 * n + 3 - i) * 2);

			if ((x = rmq(i, 2 * n + 2 - i)) * 2 - 1 > ans)

				ans = x * 2 - 1, h = i - x + 1, t = i + x - 1;

			if (i != 1 && a[i - 1] == a[i] && (x = rmq(i, 2 * n + 3 - i)) * 2 > ans)

				ans = x * 2, h = i - x , t = i + x - 1;

//			printf("%d\n", ans);

		}

		for(int i = h; i <= t; ++i)

			putchar(s[i]);

		puts("");

//		printf("%d\n", ans);

	}

	return 0;

}

第一次把调试信息放在代码里，会不会显得我很制杖呢？(水题都调了这么多)

相关文章