[CF30E] Tricky and Clever Password 题解
注意到一个合法字符串首尾相同，考虑用 S 的反转和 S 跑 KMP。
对于只有一个串，暴力 manacher 即可。
匹配到某一位置 \((i, j)\) 时，查询区间最长的奇回文串长度，用二分 + ST 表解决，因为回文串不能超过区间长度。
// Problem: Tricky and Clever Password
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-12-28 23:22:18
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
using namespace std;
const int N = 2e5 + 10;
string s, t, ss;
struct qwq {
int l1, r1, l2, r2, l3, r3, len;
bool operator < (const qwq &W) {
return len < W.len;
}
} ans;
int d[N], st[23][N], pos[23][N], lg[N];
void manacher() {
string t;
t = "$";
for(int i = 0; i < s.size(); i ++)
t += s[i], t += "#";
d[1] = 1;
for(int i = 2, l = 0, r = 0; i < t.size(); i ++) {
if(i <= r) d[i] = min(d[l + r - i], r - i + 1);
while(t[i - d[i]] == t[i + d[i]]) d[i] ++;
if(i + d[i] - 1 > r) r = i + d[i] - 1, l = i - d[i] + 1;
}
for(int i = 1; i < t.size(); i += 2) {
if(d[i] % 2 == 0) d[i] --;
st[0][i - 1 >> 1] = d[i];
pos[0][i - 1 >> 1] = (i - 1) / 2;
if(d[i] > ans.len)
ans.len = d[i], ans.l1 = (i - d[i] + 1) / 2, ans.r1 = (i + d[i] - 1) / 2 - ans.l1 + 1;
}
for(int i = 2; i <= s.size(); i ++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= lg[s.size()]; i ++)
for(int j = 0; j + (1 << i) - 1 < s.size(); j ++) {
if(st[i - 1][j] > st[i - 1][j + (1 << (i - 1))]) st[i][j] = st[i - 1][j], pos[i][j] = pos[i - 1][j];
else st[i][j] = st[i - 1][j + (1 << i - 1)], pos[i][j] = pos[i - 1][j + (1 << i - 1)];
}
}
pair<int, int> RMQ(int l, int r) {
if(l > r) return {-1, -1};
int k = lg[r - l + 1];
if(st[k][l] > st[k][r - (1 << k) + 1]) return {st[k][l], pos[k][l]};
return {st[k][r - (1 << k) + 1], pos[k][r - (1 << k) + 1]};
}
pair<int, int> query(int l, int r) { // 区间最长奇回文串
int el = 0, er = r - l + 1, ans = 0, anst = 0;
while(el <= er) {
int mid = el + er >> 1;
auto tmp = RMQ(l + (mid - (mid & 1)) / 2, r - (mid - (mid & 1)) / 2);
if(tmp.first >= mid) el = mid + 1, ans = mid, anst = tmp.second;
else er = mid - 1;
}
return {ans, anst};
}
int ne[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> s;
manacher();
ss = s;
int n = s.size();
reverse(ss.begin(), ss.end());
s = " " + s, ss = " " + ss;
for(int i = 2, j = 0; i < ss.size(); i ++) {
while(j && ss[j + 1] != ss[i]) j = ne[j];
if(ss[j + 1] == ss[i]) j ++;
ne[i] = j;
}
for(int i = 1, j = 0; i < s.size(); i ++) {
while(j && ss[j + 1] != s[i]) j = ne[j];
if(ss[j + 1] == s[i]) j ++;
if(i + j < n) {
auto t = query(i, n - j - 1);
if(ans.len < j * 2 + t.first)
ans = {i - j, j, t.second - (t.first - 1) / 2, t.first, n - j, j, j * 2 + t.first};
}
}
if(ans.l2) {
cout << 3 << '\n';
cout << ans.l1 + 1 << ' ' << ans.r1 << '\n' << ans.l2 + 1 << ' ' << ans.r2 << '\n' << ans.l3 + 1 << ' ' << ans.r3 << '\n';
}
else {
cout << 1 << '\n';
cout << ans.l1 + 1 << ' ' << ans.r1 << '\n';
}
return 0;
}