# Nemlit 的博客

By a konjac

### 题解 P4555 【[国家集训队]最长双回文串】

posted on 2019-10-29 23:02:24 | under 题解 |

（注意本身就是一个回文串的情况）

## $Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rep(i, s, t) for(int i = s; i <= t; ++ i)
#define maxn 200005
#define inf 123456789
int n, m, cnt, p[maxn], Ans, MAX = 200000, mi[maxn << 2], pax;
char c[maxn], s[maxn];
#define ls k << 1
#define rs k << 1 | 1
il void build(int k, int l, int r) {
mi[k] = inf;
if(l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
}
il void insert(int k, int l, int r, int ll, int v) {
if(l == r) return(void)(mi[k] = min(v, mi[k]));
int mid = (l + r) >> 1;
if(ll <= mid) insert(ls, l, mid, ll, v);
else insert(rs, mid + 1, r, ll, v);
mi[k] = min(mi[ls], mi[rs]);
}
il int query(int k, int l, int r, int ll, int rr) {
if(ll <= l && r <= rr) return mi[k];
int mid = (l + r) >> 1, ans = inf;
if(ll <= mid) ans = query(ls, l, mid, ll, rr);
if(mid < rr) ans = min(ans, query(rs, mid + 1, r, ll, rr));
return ans;
}
il void build() {
scanf("%s", c + 1), n = strlen(c + 1), s[++ cnt] = '~', s[++ cnt] = '#';
rep(i, 1, n) s[++ cnt] = c[i], s[++ cnt] = '#';
s[++ cnt] = '!';
}
il void solve() {
int mid = 0, mr = 0;
rep(i, 2, cnt - 1) {
if(i <= mr) p[i] = min(p[mid * 2 - i], mr - i + 1);
else p[i] = 1;
while(s[i - p[i]] == s[i + p[i]]) ++ p[i];
if(i + p[i] > mr) mr = i + p[i] - 1, mid = i;
Ans = max(Ans, i - query(1, 1, MAX, i - p[i] + 1, MAX));
insert(1, 1, MAX, i + p[i], i), pax = max(pax, p[i]);
}
if(pax - 1 == n) printf("%d", n - 1);
else printf("%d", Ans);
}
int main() {
return build(1, 1, MAX), build(), solve(), 0;
}