Manacher算法——最长回文子串的O(n)算法

发表于 分类于 Valine： 本文字数： 879 阅读时长 ≈ 1 分钟 
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
string Manacher(string s)
{
    if (s.size() < 2) return s;
    // 第一步：预处理，将原字符串转换为新字符串
    stringstream ss;
    ss << '^';
    for (int i=0; i<s.size(); i++) {
        ss << '#' << s[i];
    }
    // 尾部再加上字符$，变为奇数长度字符串
    ss << '#' << '$';
    string t = ss.str();
    // 第二步：计算数组p、起始索引、最长回文半径
    int n = t.size();
    // p数组
    vector<int> p(n);
    int id = 0, mx = 0;
    // 最长回文子串的长度
    int maxLength = -1;
    // 最长回文子串的中心位置索引
    int index = 0;
    for (int j=1; j<n-1; j++) {
        // 计算p数组
        p[j] = mx > j ? min(p[2*id-j], mx-j) : 1;
        // 向左右两边延伸，扩展右边界
        while (t[j+p[j]] == t[j-p[j]]) {
            p[j]++;
        }
        // 如果回文子串的右边界超过了mx，则需要更新mx和id的值
        if (mx < p[j] + j) {
            mx = p[j] + j;
            id = j;
        }
        // 如果回文子串的长度大于maxLength，则更新maxLength和index的值
        if (maxLength < p[j] - 1) {
            maxLength = p[j] - 1;
            index = j;
        }
    }
    // 第三步：截取字符串，输出结果
    int start = (index-maxLength)/2;
    return s.substr(start, maxLength);
}