manacher算法

manacher（马拉车）算法是用于快速查找最长回文子串的算法。基本步骤如下：

  1. 先用一个不会影响字符串的字符隔开，这样可以规避字符串长度单双数的影响。
  2. 计算每个下标位置能得到的最大回文子串长度，具体又可分为以下情况
    2.1 情况1 : i >= maxright，只能中心扩散暴力搜索
    2.2 情况2 : i < maxright，又可分为以下几类
    • 分类1: p[mirror] < maxright - i ====>> p[i] = p[mirror] < maxright - i
    • 分类2: p[mirror] == maxright - i ====>> p[i] 至少等于maxright - i，需要继续扩散
    • 分类3: p[mirror] > maxright - i ====>> p[i] = maxright - i

其中，i是对应相当下标，
p[]对应记录了当前下标的最长回文子串，
mirror是关于当前位置在当前最长回文子串中关于中间位置的镜像，
maxright是当前最长回文子串的最大右边界。

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
61
62
63
string manacher(string s) {
    string str;
    for(int i = 0; i < s.size(); i++) {
        str.push_back('#');
        str.push_back(s[i]);
    }
    str.push_back('#');
    struct Bound{
        int center = 0;
        int maxright = 0;
    };
    Bound bound;
    vector<int> matchLen(s.size(), 1);
    int cur = 0;
    while(cur < str.size() - 1) {
        // 如果当前索引在右边界之外，暴力搜索
        if(cur > bound.maxright) {
            int l = cur;
            int r = cur;
            while(l >= 0 && r < str.size() && str[l] == str[r]) {
                l--;
                r++;
            }
            bound.center = cur;
            bound.maxright = r - 1;
            matchLen[cur] = (bound.maxright - bound.center) * 2 + 1;
        }
        else {
            int mirror = bound.center - cur + bound.center;
            int mirrorleft = mirror - matchLen[mirror] / 2;
            int maxleft = bound.center - bound.maxright + bound.center;
            // 如果对称点的回文长度在边界内，当前的回文长度只会等于对称点的回文长度
            if(mirrorleft > maxleft) {
                matchLen[cur] = matchLen[mirror];
            }
            // 如果对称点的回文长度超过了边界，当前的回文长度只会等于最大边界到当前位置
            else if(mirrorleft < maxleft) {
                matchLen[cur] = (bound.maxright - cur) * 2 + 1;
            }
            // 如果正好在边界上，就继续暴力搜索
            else {
                int r = bound.maxright + 1;
                int l = cur - bound.maxright + cur - 1;
                while(l >= 0 && r < str.size() && str[l] == str[r]) {
                    l--;
                    r++;
                }
                bound.center = cur;
                bound.maxright = r - 1;
                matchLen[cur] = (bound.maxright - bound.center) * 2 + 1;
            }
        }
        cur++;
    }
    int max = 0;
    for(int i = 0; i < matchLen.size(); i++) {
        if(matchLen[i] > matchLen[max]) {
            max = i;
        }
    }
    int left = max - matchLen[max] / 2;
    return s.substr(left / 2, (matchLen[max] - 1) / 2);
}