Manacher

理念学习

解决最长回文子串问题

给出一个任意字符串，求出这个字符串中最长的回文子串

正常情况下，需要对长度奇偶不同的分类讨论。但可以用一个 $s$ 中不存在的字符，把 $s$ 中每一位隔开，再求新串中奇数长度的最长回文子串即可

对于新串 $s$ ，我们的目的是求出从它的任意位置 $i$ 出发，往两边最远能拓展出的回文子串的长度，记做 $p[i]$ (包括 $i$ 本身，所以最小为 1)

维护 $p[i]$ 的值：
维护一个到目前位置的 $R$ 最大的区间 $[L, R]$，其中 $L = M - p[M] + 1$ ($M < i$) $R = M + p[M] - 1$
$[L, R]$ 是一个回文串如果 $i \leq R$:
找到 $i$ 对于 $M$ 的对称点 $k$，此时 $i - M = M - k, k = 2 * M - i$;
此时有两种情况：
(1) 如果 $p[k]$ 对应的回文区间 $[k - p[k] + 1, k + p[k] - 1]$，不含左端点 $L$，说明这个回文区间在 $[L, R]$ 之中，此时我们可以得到 $p[i] = p[k]$
(2) 如果包含了左端点 $L$，此时 $[L, 2k-L]$ 这一端为回文串。由于 $[L, R]$ 是回文串，可得出 $[2i-R, R]$ 也是回文串。往两端暴力拓展即可。
如果 $i > R$：
暴力两端拓展即可
都要记得更新 $M, L, R$ 的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


void manacher(){
    n=s.size();
    t.resize(2*n+10);
    int m=0;
       t[0]='$';
    for(int i=0;i<n;i++){
        t[++m]=s[i],t[++m]='$';
    }
    int M=0,R=0;
    for(int i=0;i<m;i++){
        if(i>R)
            p[i]=1;
        else
            p[i]=min(p[2*M-i],R-i+1);
        while(i-p[i]>=0&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]])
            ++p[i];
        if(i+p[i]-1>R)
            M=i,R=i+p[i]-1;        
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,p[i]);
    }
    cout<<ans-1<<endl;
}

洛谷例题

P3805

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#include <bits/stdc++.h>
using namespace std;
const int N = 2e7+10;

int n,p[2*N];
string s,t;

void manacher(){
    n=s.size();
    t.resize(2*n+10);
    int m=0;
    t[0]='$';
    for(int i=0;i<n;i++){
        t[++m]=s[i],t[++m]='$';
    }
    int M=0,R=0;
    for(int i=0;i<m;i++){
        if(i>R)
            p[i]=1;
        else
            p[i]=min(p[2*M-i],R-i+1);
        while(i-p[i]>=0&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]])
            ++p[i];
        if(i+p[i]-1>R)
            M=i,R=i+p[i]-1;        
    }
    int ans=0;
    for(int i=0;i<=m;i++){
        ans=max(ans,p[i]);
    }
    cout<<ans-1<<endl;
}

int main(){
    cin>>s;
    manacher();
    return 0;
}

坑点：字符串 $t$ 要 resize，不然 re