Manacher 算法

概念讲解

什么是 Manacher 算法？

Manacher 算法是一种在 O(n) 时间内求最长回文子串的算法。

核心思想

利用已计算的回文信息，避免重复计算。

实现

1234567891011121314151617181920212223242526272829303132333435363738394041const int N = 1000005;
int p[N];  // p[i] 表示以 i 为中心的回文半径

string manacher(string s) {
    // 预处理：插入分隔符
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    
    int n = t.length();
    int center = 0, right = 0;
    int maxLen = 0, maxCenter = 0;
    
    for (int i = 0; i < n; i++) {
        if (i < right) {
            p[i] = min(right - i, p[2 * center - i]);
        } else {
            p[i] = 1;
        }
        
        while (i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        
        if (p[i] - 1 > maxLen) {
            maxLen = p[i] - 1;
            maxCenter = i;
        }
    }
    
    // 提取最长回文子串
    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

时间复杂度： O(n)

应用场景

1. 最长回文子串

1string longestPalindrome = manacher(s);

2. 回文子串计数

12345678int countPalindromes(string s) {
    // 在 manacher 中统计
    int count = 0;
    for (int i = 0; i < n; i++) {
        count += p[i] / 2;
    }
    return count;
}

考点分析

初赛考查方式

  1. 选择题： Manacher 算法的概念
  2. 程序阅读： 理解 Manacher 算法
  3. 编程题： Manacher 算法应用

常见题型

  • 最长回文子串
  • 回文子串计数

例题精讲

例题 1：最长回文子串

题目： 求字符串的最长回文子串。

解答：

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <iostream>
#include <string>
using namespace std;

const int N = 1000005;
int p[N];

string manacher(string s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    
    int n = t.length();
    int center = 0, right = 0;
    int maxLen = 0, maxCenter = 0;
    
    for (int i = 0; i < n; i++) {
        if (i < right) {
            p[i] = min(right - i, p[2 * center - i]);
        } else {
            p[i] = 1;
        }
        
        while (i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        
        if (p[i] - 1 > maxLen) {
            maxLen = p[i] - 1;
            maxCenter = i;
        }
    }
    
    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

int main() {
    string s;
    cin >> s;
    
    cout << manacher(s) << endl;
    
    return 0;
}

练习题

  1. 洛谷 P3805 Manacher
查看答案

思路：Manacher 算法模板题。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <iostream>
#include <string>
using namespace std;

const int N = 11000005;
int p[N];

int manacher(string s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    
    int n = t.length();
    int center = 0, right = 0;
    int maxLen = 0;
    
    for (int i = 0; i < n; i++) {
        if (i < right) {
            p[i] = min(right - i, p[2 * center - i]);
        } else {
            p[i] = 1;
        }
        
        while (i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        
        maxLen = max(maxLen, p[i] - 1);
    }
    
    return maxLen;
}

int main() {
    string s;
    cin >> s;
    
    cout << manacher(s) << endl;
    return 0;
}
  1. 洛谷 P4555 [国家集训队] 最长双回文串
查看答案

思路：Manacher 算法，预处理每个位置向左和向右的最长回文长度。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <iostream>
#include <string>
using namespace std;

const int N = 200005;
int p[N], l[N], r[N];

int manacher(string s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    
    int n = t.length();
    int center = 0, right = 0;
    
    for (int i = 0; i < n; i++) {
        if (i < right) {
            p[i] = min(right - i, p[2 * center - i]);
        } else {
            p[i] = 1;
        }
        
        while (i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        
        // 记录以 i 为中心的回文串的右端点
        r[i - p[i] + 1] = max(r[i - p[i] + 1], p[i] - 1);
        // 记录以 i 为中心的回文串的左端点
        l[i + p[i] - 1] = max(l[i + p[i] - 1], p[i] - 1);
    }
    
    // 传递
    for (int i = 1; i < n; i += 2) {
        r[i] = max(r[i], r[i - 2] - 2);
    }
    for (int i = n - 2; i >= 0; i -= 2) {
        l[i] = max(l[i], l[i + 2] - 2);
    }
    
    int ans = 0;
    for (int i = 0; i < n - 2; i += 2) {
        if (r[i] > 0 && l[i + 2] > 0) {
            ans = max(ans, r[i] + l[i + 2]);
        }
    }
    
    return ans;
}

int main() {
    string s;
    cin >> s;
    
    cout << manacher(s) << endl;
    return 0;
}
  1. 洛谷 P1659 [国家集训队] 拉拉队排练
查看答案

思路：Manacher 算法，统计回文串数量。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <iostream>
#include <string>
using namespace std;

const int N = 1000005;
int p[N];

int main() {
    int n;
    long long m;
    cin >> n >> m;
    
    string s;
    cin >> s;
    
    string t = "#";
    for (char c : s) {
        t += c;
        t += "#";
    }
    
    int len = t.length();
    int center = 0, right = 0;
    
    for (int i = 0; i < len; i++) {
        if (i < right) {
            p[i] = min(right - i, p[2 * center - i]);
        } else {
            p[i] = 1;
        }
        
        while (i - p[i] >= 0 && i + p[i] < len && t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    
    // 统计奇数长度回文串
    int count[n + 1];
    for (int i = 0; i <= n; i++) count[i] = 0;
    for (int i = 0; i < len; i++) {
        if (i % 2 == 1) {
            count[p[i] - 1]++;
        }
    }
    
    // 从大到小累加
    for (int i = n - 1; i >= 1; i--) {
        count[i] += count[i + 1];
    }
    
    long long ans = 0;
    for (int i = n; i >= 1; i--) {
        if (count[i] >= m) {
            ans += m * i;
            m = 0;
            break;
        } else {
            ans += count[i] * i;
            m -= count[i];
        }
    }
    
    if (m > 0) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    
    return 0;
}

易错点

⚠️ 注意：

  1. Manacher 算法要预处理字符串
  2. 臂长概念是关键
  3. Manacher 算法是 O(n) 的
  4. 注意边界处理