例题：leetcode-5

1. 引子

在一串字符串里找出最长回文串的问题，可以通过暴力求解法来解决，其时间复杂度为O(n^2)，这当然不会很快。算法的设计，就是为了让计算机能够更加高效地处理问题。我们希望可以降低时间复杂度，在1975一位名叫Manacher的人提出了这种算法，虽然牺牲了空间复杂度，让时间复杂度降为O(n)

2. 算法细节

2.1 预处理

马拉车算法首先对我们输入的默认字符串进行一次预处理，即给所有字符的左右两边添加上一个相同的符号，比如“#”。假设原始字符串为"aabca"，那么预处理过后就变成了“#a#a#b#c#a#”。为什么要这样做？我们在寻找最长字符串时，要做的事情就是以某一个值或者两个值为中心，向两边扩展，去对比左右两边的值是否匹配。这里就会有一个问题，取决于回文串本身是奇数还是偶数，相应的中心可能是一个值或者两个值。通过添加额外字符，让所有回文串都变为奇数，这就简化了寻找基准。不过这也相应的让空间复杂度由O(1)变为了O(n)。

原字符（奇）：aba 添加额外字符后（奇）：#a#b#a#

原字符（偶）：bb 添加额外字符后（奇）：#b#b#

不过只是添加了“#”还不够，为了能够准确地区分出字符串的头部和尾部，避免搜索时出现下标溢出的情况，需要在字符串头部和尾部分别添加一个与“#”和原始字符不同的字符，保证这俩字符永远也不会和其他字符组合成回文串。这里我们给头部添加一个符号“^”，给尾部添加一个符号“%”。这样，完整的处理效果如下：

处理后字符串：^#a#b#a#%

2.2 算法描述

已经对原始字符串做完预处理，现在可以开始找最长字符串了。这里引入几个概念：

$C$——中心值的下标，要求以其为下标时，半径$R$必须最大

$P[i]$——（除开首尾字符）以各个字符为中心时，相应的最长半径

$R$——以$C$为中心时，其右端最远处的下标值。计算方式为 $P[C]+C$

$Start$——最长字符串（在原始字符串中）起始索引。计算方式为 $(C-P[C])/2$

想要找到最长字符串，其实就是去找到拥有最大半径的那个中心点。另外，通过比较所有$P[i]$的值，可以得到拥有最长半径的MaxLen及最长半径P[MaxLen]和起始索引start，那么就可以准确定位最长字符串的位置了。 接下来就开始遍历搜索吧，不过别急，这里我们可以借助回文的特性，通过一些额外的技巧让搜索更具效率。 这个技巧的核心理念是：如果已经发现了长回文，那么包含在长回文中的左边的短回文在右边肯定也是短回文。 这里其实利用了对称的想法，假若我们此刻的中心点为$C$，迭代的指针为$i$，那么右边的$i$相对于中心点$C$在左边应该可以找到一个相对的点 $i_{mirror}$： $i_{mirror}$——与$i$相对于$C$对称。计算方式为 $2*C-i$ 考虑$i$与$R$的关系：

• $i<R$ 考虑$i_{mirror}$，可以为$P[i]$附上一个初始值。

  • $P[i_{mirror}] + i< =R$ 令$P[i] = R - i$ （因为超过了中心$C$的管辖范围，我们无法判断超出部分是否与之前的值能够形成回文，所以从超出部分开始匹配搜索）

  • 否则，令$P[i]=P[i_{mirror}]$

• $i==R$，无需考虑$i_{mirror}$，直接令$P[i]=0$开始进行扩展。

• 无需考虑$i>R$，因为一旦出现更大的$R$，$C$就需要更新。这就保证$i$所指向的值至少等于$R$

在确定$P[i]$的值后，以此为基础确认左右两端的下标值进行扩展搜索，可以有效节约搜索时间。

 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

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

string preProcess(string s) {
    int n = s.length();
    if (n == 0) {
        return "^%";
    }
    string ret = "^";
    for (int i = 0; i < n; i++){
        ret += "#";
        ret += s[i];
        }
    ret += "#%";
    return ret;
}

string LongestPair(string s){
    if(s=="") return s;
    string S = preProcess(s);
    int n = S.size();
    int P[n];
    int C=0, R=0;
    for(int i=1; i<n-1; ++i){
        int i_mirror = 2*C - i;
        if(R>i){
            P[i]=min(R-i, P[i_mirror]);     //P[i_mirror]+i>R时，取R-i；
        }
        else{
            P[i]=0;     // 等于R的情况
        }
        // 确定了P[i]的值后，开始进行中心扩展
        while (S[i+1+P[i]] == S[i-1-P[i]]){
            P[i]++;
        }
        // 判断是否需要更新 R
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
    }
    // 找出 P 的最大值并计算相应的初始索引
    int centerIndex = 1;
    for (int i = 2; i < n - 1; i++) {
        if (P[i] > P[centerIndex]) {
            centerIndex = i;
        }
    }
    int start = (centerIndex - P[centerIndex]) / 2; //起始索引值
    return s.substr(start, P[centerIndex]);
}