Definition

定义一个回文串为从字符串两侧向中心扫描时，左右指针指向得字符始终相同的字符串。

使用manacher算法可以在线性时间内求解出一个字符串的最长回文子串。

Solution

考虑回文串有两种：第一种对称轴在两字符之间，另一种对称轴在一个字符中心。这样分情况讨论十分不方便，我们使用一种奇技淫巧将之统一成长度为奇数的回文串，即对称轴在字符中心：将原串每两个字符之间都添加一个相同的、不在原串中的字符。显然长度为偶数的回文串对称轴会在添加的字符上，问题就得到了解决。例如：

接着发现一个回文半径为len的新串，对应老串的回文长度为len-1。证明可以根据老串的对称中心分类讨论。

于是对于每一个回文中心记录一个len作为新串的以它为中心的回文子串长度，问题就转化为了求len数组。

接着继续分类讨论：

我们从左向右扫描数组，扫描到\(i\)时，\(\forall~j~<~i\)，\(len_j\)都已经被算出来了。

我们设一个辅助变量pos为当前所有回文子串中，右端点最靠右的回文子串的右端点位置，然后对每个pos记录它是哪个回文中心延伸而成的，即为pre。下面可以分两种情况讨论：

一、\(i~\leq~pos\)

这种情况下，\(i\)一定在pos所在的回文串内部，我们找到\(i\)关于\(pre_{pos}\)的对称点\(j\)，再次分两种情况讨论：

1、1 \(len_j~<~pos~-~i\)

这也就说明以\(j\)为回文中心的回文子串是大回文子串的子串，因为\(i\)也属于大回文子串，所以\(j\)所在的回文子串也是关于\(pre_{pos}\)对称的，于是显然有\(len_i~=~len_j\)

1、2 \(len_j~\geq~pos~-~i\)

这说明以\(j\)为中心的回文子串不是大回文子串的内部，但是一直到大回文子串的边界它的回文性质都是成立的，因为对称性，所以\(i~\sim~pos\)的回文性质都是成立的，于是可以从\(pos~+~1\)开始暴力判断。

二、\(i~>~pos\)

这种情况下，没有能与\(i\)对称的位置，直接暴力向后扫描。

考虑复杂度：

发现每次暴力判断，pos一定会增加，于是最多暴力判断\(O(n)\)次。剩下的操作都是\(O(1)\)。于是复杂度为\(O(n)\)

Example

P3805manacher算法

Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

Input

一行一个字符串

Output

一行一个数表示答案

Hint

长度小于1.1e8，保证数据合法。

Solution

板子题要啥solution

Code

#include <cstdio>

#include <algorithm>

#ifdef ONLINE_JUDGE

#define freopen(a, b, c)

#endif

#define rg register

#define ci const int

#define cl const long long

typedef long long int ll;

namespace IPT {

    const int L = 1000000;

    char buf[L], *front=buf, *end=buf;

    char GetChar() {

        if (front == end) {

            end = buf + fread(front = buf, 1, L, stdin);

            if (front == end) return -1;

        }

        return *(front++);

    }

}

template <typename T>

inline void qr(T &x) {

    rg char ch = IPT::GetChar(), lst = ' ';

    while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();

    while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();

    if (lst == '-') x = -x;

}

template <typename T>

inline void ReadDb(T &x) {

    rg char ch = IPT::GetChar(), lst = ' ';

    while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();

    while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();

    if (ch == '.') {

        ch = IPT::GetChar();

        double base = 1;

        while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();

    }

    if (lst == '-') x = -x;

}

namespace OPT {

    char buf[120];

}

template <typename T>

inline void qw(T x, const char aft, const bool pt) {

    if (x < 0) {x = -x, putchar('-');}

    rg int top=0;

    do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10);

    while (top) putchar(OPT::buf[top--]);

    if (pt) putchar(aft);

}

const int maxn = 22000010;

char MU[maxn], temp[maxn];

int lenth[maxn], pre[maxn], pos;

int main() {

    freopen("1.in", "r", stdin);

    int len = 0;

    while(~(MU[++len] = IPT::GetChar()));

    MU[len--] = '\0';

    temp[0] = '$';

    for (rg int i = 1; i <= len; ++i) temp[(i << 1) - 1] = '$' , temp[i << 1] = MU[i];

    temp[len = (len << 1) + 1] = '$';

    for (rg int i = 1; i <= len; ++i) {

        if (i <= pos) {

            int mid = pre[pos], j = (mid << 1) - i;

            if (lenth[j] < (pos - i)) lenth[i] = lenth[j];

            else {

                j = (i << 1) - pos;

                while(temp[j] == temp[pos]) ++pos,--j;

                pre[--pos] = i; lenth[i] = pos - i + 1;

            }

        } else {

            pos = i; int j = i;

            while(temp[j] == temp[pos]) ++pos,--j;

            pre[--pos] = i; lenth[i] = pos - i + 1;

        }

    }

    int ans = 0;

    for (rg int i = 1; i <= len; ++i) {

        ans = std::max(ans, lenth[i]);

    }

    qw(ans - 1, '\n', true);

    return 0;

}

Summary

我可总算把智推两个月的manecher学完了……

巴特西

【字符串】manacher算法

Definition

Solution

一、\(i~\leq~pos\)

1、1 \(len_j~<~pos~-~i\)

1、2 \(len_j~\geq~pos~-~i\)

二、\(i~>~pos\)

考虑复杂度：

Example

Description

Input

Output

Hint

Solution

Code

Summary

最新文章

热门文章