P3893 [GDOI2014] Beyond 题解
思路
称第一个字符串为 \(A\)，第二个字符串 \(B\)。
考虑枚举环长 \(L\)，那么如果 \(L\) 是可行的，当且仅当存在一个位置 \(i\)，使得 \(A_{1\sim i} = B_{L - i + 1, L}, A_{i + 1\sim L} = B_{1, L - i}\)，也就是 \(A_{1\sim L}\) 的一个前缀和 \(B_{1\sim L}\) 的一个后缀匹配，且此处 \(A_{1\sim L}\) 的后缀与 \(B_{1\sim L}\) 的前缀匹配。
固定 \(L\) 之后可以暴力去寻找 \(i\)，但是之后这个方向就很难突破了，所以考虑固定 \(i\)，寻找最长的 \(L\)，如果设 \(j = L - i\)，就转化为寻找最大合法的 \(j\)，发现这个形式很像 ExKMP，则如果求出了 \(l = \text{LCP}(A_{1\sim i}, B)\)，那么对于所有 \(j\in_{1, l}\)，\(A_{i + 1, i + j} = B_{1\sim j}\)，而对于更大的 \(j\)，都是不合法的。
但是当 \(j = l\) 的时候，有可能没法满足第一个约束，即 \(A_{1\sim i} = B_{j + 1, i + j}\)，所以朴素的做法是枚举所有的 \(j\)，然后判断 \(\text{LCP}(B_{j + 1, i + j}, A) \ge i\)，如果满足这个条件，就可以缩短最长公共前缀来找到一个刚好满足条件的位置。
为了优化做法，用式子表示出来：
发现底下的式子是二维偏序，所以可以用树状数组解决这个问题。
具体而言，从大到小枚举 \(i\)，每次把所以满足 \(\text{LCP}(B_{j + 1, i + j}, A) \ge i\) 的 \(j\) 加入树状数组中，然后每次查询：
这样就是前缀 \(\max\)，也就可以用树状数组维护。
上述 \(\text{LCP}\) 的值都可以通过 ExKMP 求得。
时间复杂度：\(O(n\log n)\)。
// Problem: P3893 [GDOI2014] Beyond
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-12-21 23:25:40
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e6 + 10, M = 2e6 + 10;
int n;
int z1[N], z2[N], exz1[N], exz2[N];
string a, b;
void Z(string s, int z[]) {
z[1] = s.size();
for(int i = 2, l = 0, r = 0; i < s.size(); i ++) {
if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
while(i + z[i] < s.size() && s[i + z[i]] == s[z[i] + 1]) z[i] ++;
if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
}
void exkmp(string a, string b, int z[], int p[]) {
Z(a, z);
for(int i = 1, l = 0, r = 0; i < b.size(); i ++) {
if(i <= r) p[i] = min(z[i - l + 1], r - i + 1);
while(p[i] + 1 < a.size() && i + p[i] < b.size() && a[p[i] + 1] == b[i + p[i]]) p[i] ++;
if(i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
}
}
struct BIT {
int tr[N];
void update(int i, int c) { for (; i <= n; i += i & -i) tr[i] = max(c, tr[i]); }
int query(int i) { int res = -1e9; for (; i; i &= i - 1) res = max(res, tr[i]); return res; }
void clear() {memset(tr, -0x3f, sizeof tr);}
} bit;
int h[N], ne[M], e[M], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> a >> b;
a = "$" + a, b = "$" + b;
exkmp(a, b, z1, exz1);
exkmp(b, a, z2, exz2);
int ans = 0;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++)
add(exz1[i + 1], i);
bit.clear();
for(int i = n; i; i --) {
for(int j = h[i]; ~j; j = ne[j])
bit.update(e[j], e[j]);
ans = max(ans, i + bit.query(exz2[i + 1]));
}
cout << ans << '\n';
return 0;
}