[SHOI 2011]双倍回文

时间：2023-03-09 16:17:09
[SHOI 2011]双倍回文

Description

题库链接

记一个字符串为 \(X\) ，它的倒置为 \(X^R\) 。现在给你一个长度为 \(n\) 的字符串 \(S\) ，询问其最长的形同 \(XX^RXX^R\) 的子串长度为多少。

\(1\leq n\leq 500000\)

Solution

显然求回文之类的东西还是要 \(manacher\) 的。

假设我们求出了 \(manacher\) 的 \(len\) 数组，考虑怎么去用这个 \(len\) 。

值得肯定的是我们可以用 \(len\) 来刻画“双倍回文”。对于双倍回文的中点 \(x\) ，考虑记其第三段为 \((x,y-1)\) 。

显然我们可以去枚举 \(x\) ，然后去找离 \(x\) 最远的 \(y\) 。

我们可以用不等式 \(\begin{cases} \begin{aligned} x &\geq y-len_y \\ y &\leq x+\frac{len_x}{2} \end{aligned} \end{cases}\) 来刻画一对 \((x,y)\) 。

现在就变成了枚举 \(x\) 然后去找一个满足上述情况对应的最大的 \(y\) 。

排序+ \(set\) 维护即可。

Code

//It is made by Awson on 2018.3.16

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

const int N = 500000;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, loc, len[(N<<1)+5], f[N+5];

char s[N+5], ch[(N<<1)+5];

struct tt {

    int id, x;

    bool operator < (const tt &b) const {return id-x < b.id-b.x; }

}a[N+5];

set<int>S;

void work() {

    read(n); scanf("%s", s+1);

    for (int i = 1; i <= n; i++) ch[++loc] = '#', ch[++loc] = s[i];

    ch[++loc] = '#', ch[++loc] = '$';

    int mx = 0, po = 0;

    for (int i = 1; i <= loc; i++) {

    if (mx > i) len[i] = Min(len[(po<<1)-i], mx-i);

    else len[i] = 1;

    while (ch[i+len[i]] == ch[i-len[i]]) ++len[i];

    if (i+len[i] > mx) mx = i+len[i], po = i;

    }

    for (int i = 1; i <= n; i++) f[i] = a[i].x = ((len[(i<<1)+1]-1)>>1), a[i].id = i;

    sort(a+1, a+n+1); loc = 1; int ans = 0;

    for (int i = 1; i <= n; i++) {

    while (loc <= n && a[loc].id-a[loc].x <= i) S.insert(a[loc].id), ++loc;

    set<int>::iterator it = S.upper_bound(i+(f[i]>>1));

    if (it == S.begin()) continue;

    int t = *(--it)-i; ans = Max(ans, t);

    }

    writeln(ans<<2);

}

int main() {

    work(); return 0;

}

相关文章