「JSOI2016」扭动的回文串

发表于

题目描述

problem

数据范围100000

算法讨论

对于前两种情况，马拉车即可

对于第三种情况，我们考虑枚举这个回文串的中点位置。

首先中点位置在它所在的串上肯定往两边扩展越长越好，这个我们用马拉车的rad数组已经处理好。

这时候回文串要加长的话，以中点在A上x位置为例，肯定在A的$x-rad[x]$位置起左侧和B的$x+rad[x]-2$位置起右侧，这个我们二分+HASH判定即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 200005;

char __buf_[1 << 20], *__p1_, *__p2_;
#define GC (__p1_ == __p2_ && (__p2_ = (__p1_ = __buf_) + fread(__buf_, 1, 1000000, stdin), __p1_ == __p2_) ? 0 : *__p1_ ++)
inline int _R() {
	int d; char t;
	while (t = GC, t < '0' || t > '9') ;
	d = t - '0';
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return d;
}
inline int _S(char *c) {
	char *t = c, ch;
	while (ch = GC, ch == ' ' || ch == '\n' || ch == '\r') ;
	*t ++ = ch;
	while (ch = GC, ch != ' ' && ch != '\n' && ch != '\r') *t ++ = ch;
	*t = 0;
	return t - c;
}

int n, m;
int ra[N], rb[N];
char A[N], B[N], buf[N];

typedef unsigned int uint;
const uint P = 133;
uint ha[N], hb[N], _pow[N];

uint getha(int l, int r) {
	return ha[r] - ha[l - 1] * _pow[r - l + 1];
}
uint gethb(int l, int r) {
	return hb[l] - hb[r + 1] * _pow[r - l + 1];
}

int manacher(char *c, int *r) {
	int Max = 0, Pos = 0, ret = 0;
	for (int i = 1; i <= m; i ++) {
		r[i] = Max > i ? min(r[Pos * 2 - i], Max - i) : 1;
		while (c[i - r[i]] == c[i + r[i]]) r[i] ++;
		if (i + r[i] > Max) Max = i + r[i], Pos = i;
		ret = max(ret, r[i]);
	}
	return ret - 1;
}

int main() {
	int i, j, k, l, r, mid, tmp, p1, p2, ans = 0;
	n = _R();

	_S(buf);
	A[m = 1] = '#';
	for (i = 0; i < n; i ++) A[++ m] = buf[i], A[++ m] = '#';
	_S(buf);
	B[m = 1] = '#';
	for (i = 0; i < n; i ++) B[++ m] = buf[i], B[++ m] = '#';

	_pow[0] = 1;
	for (i = 1; i <= m; i ++) _pow[i] = _pow[i - 1] * P;
	for (i = 1; i <= m; i ++) ha[i] = ha[i - 1] * P + A[i];
	for (i = m; i >= 1; i --) hb[i] = hb[i + 1] * P + B[i];

	ans = max(ans, manacher(A, ra));
	ans = max(ans, manacher(B, rb));

	// printf("%d\n", m);
	// printf("%u %u\n", getha(3, 6), gethb(8, 11));
	// for (i = 1; i <= m; i ++) printf("%u%c", ha[i], i == m ? '\n' : ' ');
	// for (i = 1; i <= m; i ++) printf("%u%c", hb[i], i == m ? '\n' : ' ');

	for (i = 1; i <= m; i ++) {
		p1 = i - ra[i], p2 = i + ra[i] - 2;
		l = 1, r = min (p1, m - p2 + 1), tmp = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (getha(p1 - mid + 1, p1) == gethb(p2, p2 + mid - 1)) l = mid + 1, tmp = mid;
			else r = mid - 1;
		}
		ans = max(ans, tmp + ra[i] - 1);
	}

	for (i = 1; i <= m; i ++) {
		p1 = i - rb[i] + 2, p2 = i + rb[i];
		l = 1, r = min(p1, m - p2 + 1), tmp = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (getha(p1 - mid + 1, p1) == gethb(p2, p2 + mid - 1)) l = mid + 1, tmp = mid;
			else r = mid - 1;
		}
		ans = max(ans, tmp + rb[i] - 1);
	}

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