manacher算法求解最长回文串 && 回文串的相关算法

文章目录

• • 回文串问题
  • • • 是否为 回文串 / 回文数？
      • 回文子串的问题
      • • • 最长回文子串的问题
      • manacher算法
      • • • 分析
          • 代码段

回文串问题

回文串就简单理解为中心对称的字符串。这个概念理解起来还是蛮简单的。
关于回文串的题目，相对而言最简单的无疑就是求解是否为回文串！

是否为 回文串 / 回文数？

这时候就有根据数据类型去做判断。

字符串中都是数字的。我们叫做回文数。
-判断是否为回文数？题目链接

• 可以整合以下思路：
  1、 转化为字符串去处理？可行！见下。但是会用到大量的额外空间。
  2、数字翻转？有可能超过INT_MAX。如果long long 的去存其实也能做出来。
  3、就是上面链接的一种做法。翻转一半数字。

• 翻转一半数字：链接中的思路是一个 log(n)时间复杂度和 1 的空间复杂度的解法。
  1、小于0的数字不是回文数；
  2、个位为0且数字位数不为1的，不是回文数；

• 该方法的难点是如何判断翻转到了一半：翻转数字大于被反转数字！

• 巧妙出，返回值为 return x == reversr || x == reverse / 10;，如果被反转的数字位数为奇数，则用x==reverse/10来判断；如果为偶数，用x==reverse来判断。

字符串中的字符有符号，char或int等等的 ，我们叫做回文串。
判断是否为回文串？题目链接
这道题就是通用的求回文串的方法。包括回文数字也可以转化成回文串处理。
常规做法有 栈，reverse，双指针。

• 这道题更好的方法是双指针。
  可以直接看题解。双指针的用法很广泛，快排就是用同向双指针做的。

回文子串的问题 最长回文子串的问题

重点：回文串是有偶数位和奇数位之分的。
题目链接

• 解决方案一：动态规划

该方案是最容易理解的方案，有着O(n2)的时间复杂度和O(n2)的空间复杂度，建立dp[i][j]来显示字符串中从i到j下标的字符串是否为回文串。这个可以自己找资料去了解动态规划。

• 解决方案二：中心拓展法

• 该方案利用双指针和遍历，有着O(n2)的时间复杂度和O(1)的空间复杂度.遍历下标为index的位置，从index开始向两边扩展。同时从index和index+1向两边扩展。//因为回文串是有偶数位和奇数位之分的。

• 解决方案三： manacher算法

• 该方案是线性查找回文串的方法。也是本文的重点。也就是时间复杂度位O(N)的算法。

manacher算法 分析

针对字符串“abcbaade"查找最长回文子串的实现步骤先给你：

1. 首先我们解决下奇数和偶数的问题，在每个字符间插入"#"，并且为了使得扩展的过程中，到边界后自动结束，在两端分别插入 “^” 和 “$”，两个不可能在字符串中出现的字符。经过处理，字符串的长度永远都是奇数了。
   

2. 首先我们用一个数组 P 保存从中心扩展的最大个数，而它刚好也是去掉 “#” 的原字符串的总长度。例如下图中下标是 6 的地方。可以看到 P[ 6 ] 等于 5，所以它是从左边扩展 5 个字符，相应的右边也是扩展 5 个字符，也就是 "#c#b#c#b#c#"。而去掉 # 恢复到原来的字符串，变成 "cbcbc"，它的长度刚好也就是 5。
   

3. 求原字符串下标
   用 P 的下标 i 减去 P [ i ]，再除以 2 ，就是原字符串的开头下标了。
   例如我们找到 P[ i ] 的最大值为 5 ，也就是回文串的最大长度是 5 ，对应的下标是 6 ，所以原字符串的开头下标是 （6 - 5 ）/ 2 = 0 。所以我们只需要返回原字符串的第 0 到 第 （5 - 1）位就可以了。

4. 求每个 P [ i ]
   接下来是算法的关键了，它充分利用了回文串的对称性。//看不懂的可以看下代码。
   我们用 C 表示回文串的中心，用 R 表示回文串的右边半径。所以 R = C + P[ i ] 。C 和 R 所对应的回文串是当前循环中 R 最靠右的回文串。
   让我们考虑求 P [ i ] 的时候，如下图。
   用 i_mirror 表示当前需要求的第 i 个字符关于 C 对应的下标。
   

我们现在要求 P [ i ]， 如果是用中心扩展法，那就向两边扩展比对就行了。但是我们其实可以利用回文串 C 的对称性。i 关于 C 的对称点是 i_mirror ，P [ i_mirror ] = 3，所以 P [ i ] 也等于 3 。
但是有三种情况将会造成直接赋值为 P [ i_mirror ] 是不正确的，下边一一讨论。

1. 超出了 R
   当我们要求 P [ i ] 的时候，P [ mirror ] = 7，而此时 P [ i ] 并不等于 7 ，为什么呢，因为我们从 i 开始往后数 7 个，等于 22 ，已经超过最右的 R ，此时不能利用对称性了，但我们一定可以扩展到 R 的，所以 P [ i ] 至少等于 R - i = 20 - 15 = 5，会不会更大呢，我们只需要比较 T [ R+1 ] 和 T [ R+1 ]关于 i 的对称点就行了，就像中心扩展法一样一个个扩展。
   
2. P [ i_mirror ] 遇到了原字符串的左边界
   此时P [ i_mirror ] = 1，但是 P [ i ] 赋值成 1 是不正确的，出现这种情况的原因是 P [ i_mirror ] 在扩展的时候首先是 “#” == “#” ，之后遇到了 "^"和另一个字符比较，也就是到了边界，才终止循环的。而 P [ i ] 并没有遇到边界，所以我们可以继续通过中心扩展法一步一步向两边扩展就行了。
   
3. i 等于了 R
   此时我们先把 P [ i ] 赋值为 0 ，然后通过中心扩展法一步一步扩展就行了

5. 考虑 C 和 R 的更新
   就这样一步一步的求出每个 P [ i ]，当求出的 P [ i ] 的右边界大于当前的 R 时，我们就需要更新 C 和 R 为当前的回文串了。因为我们必须保证 i 在 R 里面，所以一旦有更右边的 R 就要更新 R。
   

此时的 P [ i ] 求出来将会是 3 ，P [ i ] 对应的右边界将是 10 + 3 = 13，所以大于当前的 R ，我们需要把 C 更新成 i 的值，也就是 10 ，R 更新成 13。继续下边的循环。

代码段

这是题解的代码：

public String preProcess(String s) {
    int n = s.length();
    if (n == 0) {
        return "^$";
    }
    String ret = "^";
    for (int i = 0; i < n; i++)
        ret += "#" + s.charAt(i);
    ret += "#$";
    return ret;
}

// 马拉车算法
public String longestPalindrome2(String s) {
    String T = preProcess(s);
    int n = T.length();
    int[] P = new int[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] = Math.min(R - i, P[i_mirror]);// 防止超出 R
        } else {
            P[i] = 0;// 等于 R 的情况
        }

        // 碰到之前讲的三种情况时候，需要利用中心扩展法
        while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
            P[i]++;
        }

        // 判断是否需要更新 R
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }

    }

    // 找出 P 的最大值
    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
    return s.substring(start, start + maxLen);
}

时间复杂度：for 循环里边套了一层 while 循环，难道不是 O ( n² )？不！其实是 O ( n )。不严谨的想一下，因为 while 循环访问 R 右边的数字用来扩展，也就是那些还未求出的节点，然后不断扩展，而期间访问的节点下次就不会再进入 while 了，可以利用对称得到自己的解，所以每个节点访问都是常数次，所以是O ( n )。
空间复杂度：O（n）

这是自己的复盘的代码：

// "manacher.cpp"
#include
#include

//加上g++ -D D manacher.cpp 添加调试信息。
#ifdef D
#define DBG(fmt,arg...) printf(fmt,##arg)
#else
#define DBG(fmt,arg...)  
#endif

using namespace std;

string manacher(string& s){

    string tmp;
    for(int i = 0; i < s.size(); ++i){
        tmp.push_back('#');
        tmp.push_back(s[i]);
    }
    tmp.push_back('#');
    DBG("%s\n",tmp);
    int n = tmp.size();
    int p[n];
    
    int c = 0, r = 0, i_mirror = 0;
    //c是中心点，r是最右回文边界.
    
    for(int i = 0; i < n; ++i){
        i_mirror = 2 * c - i;
        if(r > i){
        //如果i此时再r内，说明他在之前某个回文串的一部分，此时可以使用p[i_mirrot]来获得已知的回文半径，大大缩短时间）
            p[i]=min(r-i,p[i_mirror]); 
        }else{
            p[i]=0;
        }
        //常规的中心拓展，不过加了p[i]，使得中心拓展的其实有效范围变大了。
        while(i-1-p[i]>=0 && i+1+p[i]<n && tmp[i - 1- p[i]] == tmp[i + 1 + p[i]])p[i]++;
        //更新最右回文边界，用来初始化后面的回文边界包含的i的p[i]初始值。
        if(i+p[i] > r){
            c = i;
            r = i + p[i];
            DBG("c=%d,r=%d",c,r);
        }
        DBG("%d\n",i);
    }
    DBG("TEST1 END\n");
    int max_len = 0, center = 0;
    for(int i = 0; i < n; ++i){
        if(p[i] > max_len){
            max_len = p[i];
            center = i;
        }
    }
    DBG("TEST2 END\n");

    int start = (center - max_len) / 2;
    return s.substr(start,max_len);
}

int main(){
    string s;
    getline(cin,s);
    cout << manacher(s);
    return 0;
}