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

~~不知道有没有人跟我一样数据结构学傻了~~ 首先这道题是要求回文串，那么我们可以想到[manacher算法](https://www.luogu.org/blog/tbr-blog/solution-p3805) 但由于$manacher$不能求出双回文子串，我们要考虑一些性质 首先对于一个回文串，删掉两边的字符它一样是回文串 然后$manacher$求出的$p$数组就是他能拓展的数量，发现对于一个点对$i, j$，当满足$i+p_i+1≥j-p_j+1$时，两个回文串有交集，根据上述性质，这对点对是可以构成双回文子串的 上述式子是可以用权值线段树实现的，每找到一个$i+p_i$，丢尽权值线段树里面，每次查询权值线段树中$[j-p_j, MAX]$的最小的$i$，用$j-i+1$更新答案即可 （注意本身就是一个回文串的情况） ## $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; } ```