manacher + exKMP + 二分。
感觉是最粗暴的方法，想出来之后自己硬莽了 4k，荣获题解区最长。
Solution
约定：下文所提及到的所有的回文串，均指奇长度回文串。
-
显然把题目拆成两个部分，中间的回文串，以及两边相同的连续子串。考虑一下从哪个入手比较好。
-
忘记是咋想的了，易得从两边相同连续子串 \(a\) 和 \(c\) 会方便些。发现，它相当于是原串 \(S\) 和它的反串 \(S'\) 做一次 exKMP，对于原串的每个位置 \(i\)，\(z_i\) 表示从这一位开始最长的合法的 \(a\) 的长度。 -
现在考虑对于确定的 \(a,c\)，如何找到最长的 \(b\)。我们发现，如果区间 \([i+z_i,n-z_i]\)（\(n\) 是最后一个下标）中最长的回文串 \(b\) 如果覆盖了整个区间，那么这就是 \(k=1\) 的情况，即 \([i,n]\) 是一整个回文串。所以，对于 \(k=3\) 的情况，\(b\) 不可能覆盖完整个 \([i+z_i,n-z_i]\) 区间，所以直接二分答案找到区间 \([i+z_i,n-z_i]\) 中的最长回文串长度即可。
-
考虑如何找到任意一个区间中最长回文串的长度。方法比较套路，二分一个长度 \(mid\)，表示查找区间中是否存在 \(2\times mid +1\) 的回文串。
check(mid)就是询问区间是否存在 \(i\in [l+mid,r-mid]\)，满足 \(p_i\geq 2\times mid +1\)，其中 \(p_i\) 表示以 \(i\) 为中心的最长回文串长度，manacher 预处理就好。 -
总复杂度 \(O(n\log n)\)，瓶颈在二分，跑了 122 ms，感觉挺不错的了。
Code
实现的话，细节就很多了。
manacher 和 exKMP 的部分直接套板子就行，注意一下 manacher 是把原串扩充之后做的，但做完得转回原串。
存答案的时候也挺麻烦的。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
const int maxn = 2e5 + 5;
int n, m;
char a[maxn], b[maxn], s[maxn << 1];
int q[maxn << 1], p[maxn];
int nxt[maxn], z[maxn];
int st[maxn][30], lg[maxn];
int ans, typ, pt[5][5];
inline void input(){
char ch = getchar();
s[0] = '~', s[m = 1] = '#';
while(ch < 'a' or ch > 'z') ch = getchar();
while(ch >= 'a' and ch <= 'z')
s[++m] = ch, s[++m] = '#', ch = getchar();
}
inline void manacher(){
int mx = 0, pos = 0;
rep(i, 1, m){
q[i] = mx > i ? min(mx - i + 1, q[pos * 2 - i]) : 1;
while(s[i + q[i]] == s[i - q[i]]) q[i] += 1;
if(i + q[i] - 1 >= mx)
mx = i + q[i] - 1, pos = i;
}
int tp = -1;
rep(i, 1, m) if(s[i] >= 'a' and s[i] <= 'z') p[++tp] = (q[i] / 2 - 1) * 2 + 1;
}
inline void getnxt(){
nxt[0] = n;
int mx = 0, pos = 1;
while(nxt[1] + 1 < n and b[nxt[1]] == b[nxt[1] + 1]) nxt[1] += 1;
mx = nxt[1];
rep(i, 2, n - 1){
nxt[i] = mx < i ? 0 : min(nxt[i - pos], mx - i + 1);
while(i + nxt[i] < n and b[i + nxt[i]] == b[nxt[i]]) nxt[i] += 1;
if(i + nxt[i] - 1 >= mx)
mx = i + nxt[i] - 1, pos = i;
}
}
inline void getz(){
int mx = 0, pos = 0;
while(z[0] < n and b[z[0]] == a[z[0]]) z[0] += 1;
mx = z[0] - 1;
rep(i, 1, n - 1){
z[i] = mx < i ? 0 : min(nxt[i - pos], mx - i + 1);
while(i + z[i] < n and a[i + z[i]] == b[z[i]]) z[i] += 1;
if(i + z[i] - 1 >= mx)
mx = i + z[i] - 1, pos = i;
}
}
inline int Max(int x, int y){ return p[x] > p[y] ? x : y;}
inline void pre_st(){
lg[0] = -1; rep(i, 1, 2e5) lg[i] = lg[i / 2] + 1;
rep(i, 0, n - 1) st[i][0] = i;
for(int j = 1; (1 << j) <= n; ++j)
for(int i = 0; (i + (1 << j) - 1) < n; ++i)
st[i][j] = Max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
inline int qry_st(int l, int r){
if(l == r) return l;
if(l > r) return 0;
int k = lg[r - l + 1];
return Max(st[l][k], st[r - (1 << k) + 1][k]);
}
int id;
inline int qry_mxlen(int L, int R){
int l = 1, r = (R - L) / 2 + 1, ans = 1; id = -L;
while(l <= r){
int mid = (l + r) >> 1, tmp;
if(p[tmp = qry_st(L + mid, R - mid)] >= mid * 2 + 1)
ans = mid, id = tmp, l = mid + 1;
else r = mid - 1;
}
if(id == -L) ans = 1, id *= -1; else ans = ans * 2 + 1;
return ans;
}
signed main(){
input();
n = -1;
rep(i, 1, m) if(s[i] >= 'a' and s[i] <= 'z') a[++n] = s[i];
rep(i, 0, n) b[n - i] = a[i];
n += 1;
manacher(), getnxt(), getz();
pre_st();
ans = 1, typ = 1, pt[1][0] = 0, pt[1][1] = 1;
rep(i, 0, n - 1) if(p[i] > ans)
ans = p[i], pt[1][0] = i - (p[i] + 1) / 2 + 1, pt[1][1] = p[i];
rep(i, 0, n - 1){
if(i + z[i] >= n - 1 - z[i]){
int len = (n - i);
if(len & 1){ if(ans >= len) continue;} else{ if(ans >= len - 1) continue;}
if(len & 1){
ans = len, typ = 1;
pt[1][0] = i, pt[1][1] = len;
} else{
ans = len - 1, typ = 3;
pt[1][0] = i, pt[1][1] = len / 2 - 1;
pt[2][0] = i + pt[1][1], pt[2][1] = 1;
pt[3][0] = pt[2][0] + 2, pt[3][1] = len / 2 - 1;
}
continue;
}
int len = qry_mxlen(i + z[i], n - 1 - z[i]),
fll = (n - 1 - z[i]) - (i + z[i]) + 1,
op = (len == fll ? 1 : 3);
if(ans >= len + z[i] * 2) continue;
ans = len + z[i] * 2, typ = op;
if(op == 1) pt[1][0] = i, pt[1][1] = ans;
else{
pt[1][0] = i, pt[1][1] = z[i];
pt[2][0] = id - (len + 1) / 2 + 1, pt[2][1] = len;
pt[3][0] = n - 1 - z[i] + 1, pt[3][1] = z[i];
}
}
printf("%lld\n", typ);
rep(i, 1, typ) printf("%lld %lld\n", pt[i][0] + 1, pt[i][1]);
return 0;
}
Thanks for reading.
标签：Tricky,exKMP,pt,int,题解,mid,len,ans,mx From： https://www.cnblogs.com/gsn531/p/17929114.html