BZOJ 2342 & manachar+最优性剪枝

时间：2021-12-15 08:28:03

题意:

　　求最长回文串,串的两边都是回文串.

Solution:

　　manachar预处理然后暴力找...

Code:

　　

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

#define MAXN 1000005

using namespace std;

int n, p[MAXN], f[MAXN], ans;

char s[MAXN];

int main()

{

    scanf("%d", &n);

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

    for(int i = n; i; i --)s[i * 2] = s[i], s[i * 2 - 1] = '*';

    s[0] = '#'; s[2 * n + 1] = '*';

    int k = 0;

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

        if(k + p[k] - 1 < i)p[i] = 1;

        else p[i] = min(p[2 * k - i], k + p[k] - i);

        while(s[i + p[i]] == s[i - p[i]])p[i] ++;

        if(i + p[i] > k + p[k])k = i;

    }

    for(int i = 1; i <= n; i ++)f[i] = (p[i * 2 + 1] - 1) / 2;

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

        for(int j = f[i] / 2; j && j * 4 > ans; j --)

            if(f[i - j] >= j && f[i + j] >= j)ans = max(ans, j * 4);

    cout << ans << endl;

    return 0;

}

相关文章