P3785 题解

First Post:

Last Update:

妙妙题，一开始打全局平衡二叉树的单 ，300 行没调出来。后来获知此题有线性做法。确实十分高妙，有一种字符串的美。

题意：给出两个字符串 ，问能否将 划分为三个子串 ，并将其以某个顺序拼接可以组合出 ，若能请构造方案。。

看到这题，当然要分六种情况：

，直接判断即可。

或 ，我们发现有两个部分实际上是一段，所以我们只需要考虑将 划为两段，枚举端点，用 Hash 判断相等即可。

这是本文要讲述的重点。

构造新串 （这个转化很妙，虽然我也不知道怎么想到的）。

那么原问题相当于把 划分为三个长度为偶数的回文串。

枚举第一个回文串 ，那么问题变为判断 是否能被划分为两个偶回文串。

这里我们需要用到回文串划分的一个结论：

那么，如果存在划分，那必有一种方案中有最长回文前缀或最长回文后缀。

也就是说，我们如果只需找到一种回文串划分，只需考虑这个串的最长回文前缀和最长回文后缀即可。

我们发现，把上述结论改成“偶回文串”，也是没有任何问题的。

对 串跑一遍 Manacher，这样任意后缀的最长回文前缀和最长回文后缀都容易递推预处理了。

具体的，设 表示 的最长回文前缀，那么有 。

这样就可以从 递推到 了，在 处再算上 的位置的贡献即可。（ 表示以 为靠右的那个回文中心时的最长回文长度的一半）。

。

枚举 ，只需令 ，然后判断是否存在偶回文划分即可。

但是我们要处理很多个 。

注意到 的最长偶回文前缀就是 在 中对应位置的最长匹配长度 ，用 KMP 跑出这个值即可。最长偶回文后缀同理。

具体细节可见代码。

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc 
	#undef flush
}
using namespace FastIO;
const int N = 1e6 + 5;
typedef unsigned long long ull;
const int base = 1333331;
int n,m;
int s[N],t[N];

int nxt[N << 1],mth[2][N << 1];
ull hsh[2][N],Pow[N];

void KMP(int *s,int *t,int n,int *mth)
{
	int j = 0;nxt[1] = 0;
	for(int i = 1;i < n;i++)
	{
		while(j && t[i + 1] != t[j + 1]) j = nxt[j];
		if(t[i + 1] == t[j + 1]) ++j;
		nxt[i + 1] = j;
	}
	j = 0;
	for(int i = 1;i <= n;i++)
	{
		while(j && s[i] != t[j + 1]) j = nxt[j];
		if(s[i] == t[j + 1]) ++j;
		if(j == i) j = nxt[j];
		mth[i] = j;
	}
}
inline int Hash(ull *hsh,int l,int r) { return hsh[r] - hsh[l - 1] * Pow[r - l + 1];}
int len[N << 1];
int mxp[N << 1],mxs[N << 1];
int ts[N << 1];
inline void work()
{
	read(n);read(m);
	for(int i = 1;i <= n;i++) read(s[i]);
	for(int i = 1;i <= n;i++) read(t[i]);
	Pow[0] = 1;
	for(int i = 1;i <= n;i++) Pow[i] = Pow[i - 1] * base;
	hsh[0][0] = 1;
	for(int i = 1;i <= n;i++) hsh[0][i] = hsh[0][i - 1] * base + s[i];
	hsh[1][0] = 1;
	for(int i = 1;i <= n;i++) hsh[1][i] = hsh[1][i - 1] * base + t[i];
	int flg = 1;
	for(int i = 1;i <= n;i++) flg &= (s[i] == t[i]);
	if(flg) { printf("YES\n1 1\n2 2\n3 %d\n",n);return;}
	for(int i = 1;i <= n;i++)
		if(Hash(hsh[1],1,i) == Hash(hsh[0],n - i + 1,n) && Hash(hsh[1],i + 1,n) == Hash(hsh[0],1,n - i))
		{
			if(i == 1) printf("YES\n%d %d\n%d %d\n%d %d\n",i + 1,i + 1,i + 2,n,1,i);
			else printf("YES\n%d %d\n%d %d\n%d %d\n",i + 1,n,1,1,2,i);
			return;
		}
	KMP(s,t,n,mth[0]);
	KMP(t,s,n,mth[1]);
	for(int i = n;i >= 1;i--)
	{
		int l = mth[0][i];
		if(l > 0 && Hash(hsh[1],l + 1,i) == Hash(hsh[0],1,i - l))
			{ printf("YES\n%d %d\n%d %d\n%d %d\n",l + 1,i,1,l,i + 1,n);return;}
		l = mth[1][i];
		if(l > 0 && Hash(hsh[0],l + 1,i) == Hash(hsh[1],1,i - l))
			{ printf("YES\n%d %d\n%d %d\n%d %d\n",i - l + 1,i,1,i - l,i + 1,n);return;}	
        if(s[i] != t[i]) break;
	}
	reverse(s + 1,s + n + 1);
	reverse(t + 1,t + n + 1);
	KMP(s,t,n,mth[0]);
	KMP(t,s,n,mth[1]);
	reverse(s + 1,s + n + 1);
	reverse(t + 1,t + n + 1);
	reverse(mth[0] + 1,mth[0] + n + 1);
	reverse(mth[1] + 1,mth[1] + n + 1);
	for(int i = 1;i <= n;i++)
	{
		int l = mth[0][i];
		if(l > 0 && Hash(hsh[0],i + l,n) == Hash(hsh[1],i,n - l))
			{ printf("YES\n%d %d\n%d %d\n%d %d\n",1,i - 1,n - l + 1,n,i,n - l);return;}
		l = mth[1][i];
		if(l > 0 && Hash(hsh[0],i,n - l) == Hash(hsh[1],i + l,n))
			{ printf("YES\n%d %d\n%d %d\n%d %d\n",1,i - 1,i + l,n,i,i + l - 1);return;}
        if(s[i] != t[i]) break;
	}
	ts[0] = m + 1;
	for(int i = 1;i <= n;i++)
		ts[2 * i - 1] = s[i],ts[2 * i] = t[n - i + 1];
	int l = 0,r = 0;
	for(int i = 1;i <= 2 * n;i++) mxp[i] = mxs[i] = 0;
	for(int i = 1;i <= 2 * n;i++)
	{
		if(r > i) len[i] = min(len[2 * l - i],r - i);
        else len[i] = 0;
		while(i + len[i] <= 2 * n && ts[i + len[i]] == ts[i - len[i] - 1])
			++len[i];
		if(i + len[i] > r)
			l = i,r = i + len[i];
		if(i + len[i] > 2 * n)
		{
			mxs[i - len[i]] = 2 * len[i];
			mxp[i - len[i] + 1] = max(mxp[i - len[i] + 1],2 * len[i] - 2);
		}
		else mxp[i - len[i]] = max(mxp[i - len[i]],2 * len[i]);
	}
	for(int i = 2;i <= 2 * n;i++) mxp[i] = max(mxp[i],mxp[i - 1] - 2);
	for(int i = 2 * n - 1;i >= 1;i--) mxs[i] = max(mxs[i],mxs[i + 1]);
	for(int i = 1;i < n;i++)
	{
		if(Hash(hsh[0],1,i) != Hash(hsh[1],n - i + 1,n))
			continue;
		int l = mxp[2 * i + 1] / 2;
		if(l > 0 && Hash(hsh[0],i + l + 1,n) == Hash(hsh[1],1,n - i - l))
			{ printf("YES\n%d %d\n%d %d\n%d %d\n",n - i + 1,n,n - i - l + 1,n - i,1,n - i - l);return;}
		l = mxs[2 * i + 1] / 2;
		if(l > 0 && Hash(hsh[0],i + 1,n - l) == Hash(hsh[1],l + 1,n - i))
			{ printf("YES\n%d %d\n%d %d\n%d %d\n",n - i + 1,n,l + 1,n - i,1,l);return;}
	}
	printf("NO\n");
}
int main()
{
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
≡