通称马拉车算法。
NOI 大纲评级：8 级（NOI 级）。

回文串

一个字符串有 O(n2)O(n^2) 个子串。事实上，存在一个算法可以在 O(n)O(n) 复杂度内找到所有回文子串。
这是利用了回文串的一个性质，若 s[l..r]s[l..r] 是回文串，则 s[l+1..r−1]s[l+1..r-1] 也是回文串。

因此，我们只需要记录以某个字符为中心的回文串的最长长度。

统一奇数偶数长度

众所周知，偶数长度回文串的中心在中间两个字符的中间，我们可以通过一些转化，使得我们只需要处理奇数长度回文串的情况。
具体来说，往每两个字符中间插入一个不存在的字符（比如说 #），特别的，为了防止越界，我们在开头加上 ^，结尾加上 $。

1
2
3
4
5
6
7
8
9
scanf("%s",stmp);int l=strlen(stmp);
s[0]='^';
s[1]='#';
int n=2;
for(int i=0;i<l;i++){
    s[n++]=stmp[i];
    s[n++]='#';
}
s[n++]='$';

例：经过这样变化后，

  • abcba 变为了 ^#a#b#c#b#a#$；
  • abba 变为了 ^#a#b#b#a#$；

这样，设 dd 数组为变化后的字符串以该字符为中心的最长回文串到中心的字符数，则可以知道，真正的回文串的长度是这个距离-1。
例：

  • 回文串 aba 找到的变化后回文串为 #a#b#a#，d=4d=4，实际长度为 3。
  • 回文串 abba 找到的变化后回文串为 #a#b#b#a#，d=5d=5，实际长度为 4。

Manacher 算法

现在我们只需要计算以每个字符为中心的 dd 数组的值即可。

设当前找到的右边界最大回文串为 (l,r)(l,r)，我们已经计算完了 d[1..i−1]d[1..i-1]，现在要计算 d[i]d[i]。

  1. i>ri>r：我们对于这种情况不做任何优化，直接一位一位字符往外拓展，直到遇到不同的字符。
  2. i≤ri\le r：令 j=l+r−ij=l+r-i，因为回文串具有对称性，基本上总有 d[i]=d[j]d[i]=d[j]。
    但是考虑这个情况：r−i+1≤d[j]r-i+1\le d[j]，这说明我们要判断的字符串已经超出原来的回文串，这部分的对称性是不能保证的，因此无法直接令 d[i]=d[j]d[i]=d[j]。我们应该令 d[i]=min⁡(d[j],r−i+1)d[i]=\min(d[j],r-i+1)。
    这时，这个回文串还可能再进行拓展，我们继续用朴素算法进行拓展即可。

可以证明，这个算法的复杂度是 O(n)O(n)（因为不难发现每次往外拓展 1 位，rr 都会增加）

模板

虽然模板很好被背，但是记住，数组要开两倍大！！！！！！
洛谷P3805 【模板】manacher 算法

还需要注意的时候，在计算 dd 数组的时候，我们从下标 11 开始计算，跳过下标 00（因为 00 往外拓展会越界），这就是我们在开头加一个不同字符的理由。

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
#include<bits/stdc++.h>
using namespace std;

const int N = 3e7;
char stmp[N];
char s[N];
int d[N];

int main(){
    scanf("%s",stmp);int l=strlen(stmp);
    s[0]='^';
    s[1]='#';
    int n=2;
    for(int i=0;i<l;i++){
        s[n++]=stmp[i];
        s[n++]='#';
    }
    s[n++]='$';
    // puts(s);

    int mid=0,r=-1;
    for(int i=1;i<n;i++){ // i=1 开始
        if(i<=r)d[i]=min(d[mid*2-i],r-i+1);
        else d[i]=1;

        while(s[i-d[i]]==s[i+d[i]])d[i]++;
        
        if(i+d[i]-1>r){
            r=i+d[i]-1;
            mid=i;
        }
    }
    printf("%d\n",(*max_element(d,d+n))-1);
    return 0;
}

例题

洛谷P4555 [国家集训队] 最长双回文串

输入长度为 nn 的串 SS，求 SS 的最长双回文子串 TT，即可将 TT 分为两部分 X,YX, Y（∣X∣,∣Y∣≥1|X|,|Y|≥1）且 XX 和 YY 都是回文串。

还是考虑先将字符串像之前一样预处理，然后跑一边马拉车。

然后，我们考虑枚举每个双回文子串的分割点：即对于一个点的位置，找出以它结尾/以它开头的最长回文子串。
事实上，这个可以用 O(n)O(n) 扫描一遍得到。
考虑现在要求以 ii 结尾的最长回文子串，一定是找到前面一个 jj，使得 j+d[j]−1≥ij+d[j]-1\ge i，事实上，可以证明，随着 ii 的增大，jj 一定不减，所以说我们可以维护 jj，每次不断加 1，直到找到一个合法的 jj。

总复杂度 O(n)O(n)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5+100;
char s[N],ss[N];
int d[N];

int lt[N],rt[N]; // 往左/右最长的回文串的长度

int main(){
    scanf("%s",ss);int len=strlen(ss);
    int n=0;
    s[n++]='^';s[n++]='#';
    for(int i=0;i<len;i++){
        s[n++]=ss[i];s[n++]='#';
    }
    s[n++]='$';

    int mid=0,r=-1;
    for(int i=1;i<n;i++){
        if(i<=r)d[i]=min(d[mid*2-i],r-i+1);
        else d[i]=1;

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

        if(i+d[i]-1>r){
            r=i+d[i]-1;mid=i;
        }
    }

    int now=0;
    for(int i=0;i<n;i++){
        if(s[i]=='#'){
            while(now<i){
                if(d[now]+now-1>=i)break;
                now++;
            }
            lt[i]=i-now;
        }
    }

    now=n-1;
    for(int i=n-2;i>0;i--){
        if(s[i]=='#'){
            while(now>i){
                if(now-d[now]+1<=i)break;
                now--;
            }
            rt[i]=now-i;
        }
    }

    int ans = 0;
    for(int i=0;i<n;i++){
        if(lt[i]&&rt[i]) // 两边都要有
            ans = max(ans,lt[i]+rt[i]);
    }
    printf("%d\n",ans);
    return 0;
}

洛谷P3501 [POI2010] ANT-Antisymmetry

对于一个 0/10/1 字符串，如果将这个字符串 00 和 11 取反后，再将整个串反过来和原串一样，就称作「反对称」字符串。比如 0000111100001111 和 010101010101 就是反对称的，而 10011001 就不是。
现在给出一个长度为 nn 的 0/10/1 字符串，求它有多少个子串是反对称的，注意这里相同的子串出现在不同的位置会被重复计算， 1≤n≤500 0001\le n\le 500\ 000 。

本题有哈希解法，复杂度 O(nlog⁡n)O(n\log n)，见「字符串哈希#Antisymmetry」。

根据上面的思想，不难对马拉车算法进行一些改造来解决本题。不难发现，对于「反对称」，我们推导马拉车所用的性质全部都还成立。只不过在字符对应有一点小变化，0 要对应 1，1 要对应 0，我们写一个 match 函数方便处理。

并且，不难发现，只有长度是偶数的才可能是反对称串。因此，我们只对 s[i]='#' 的位置进行检查。

最后一个问题是求解反对称子串的个数。若以这个为中心最长的长度为 xx，则以这个为中心有 x2\frac x 2 个反对称串。（找规律）

复杂度为 O(n)O(n)，明显优于哈希解法。

不要忘记开 long long……

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
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;

const int N = 2e6;

char ss[N],s[N];
int d[N];

bool match(char a,char b){
    if(a=='0')return b=='1';
    if(a=='1')return b=='0';
    if(a=='#')return b=='#';
    return 0;
}

int main(){
    int k;
    scanf("%d%s",&k,ss);
    int n=0;
    s[n++]='^';s[n++]='#';
    for(int i=0;i<k;i++){
        s[n++]=ss[i];s[n++]='#';
    }
    s[n++]='$';

    int mid=0,r=-1;
    long long ans = 0;
    for(int i=1;i<n;i+=2){ // 只用检查长度为偶数的

        if(i<=r)d[i]=min(d[mid*2-i],r-i+1);
        else d[i]=1;

        while(match(s[i-d[i]],s[i+d[i]]))d[i]++;

        if(i+d[i]-1>r){
            r=i+d[i]-1;
            mid=i;
        }

        ans += (d[i]-1)/2; // 子串个数
    }
    printf("%lld\n",ans);

    return 0;
}