左神算法进阶班1_4Manacher算法

朴灿烈づ我的快乐病毒、 2022-01-06 00:01 176阅读 0赞

1 #include <iostream>
     2 #include <string>
     3 
     4 using namespace std;
     5 
     6 //使用manacher算法寻找字符中最长的回文子串
     7 
     8 int Manacher(string str)
     9 {
    10     //字符串预处理
    11     string newStr = "#";
    12     for (auto c : str)
    13         newStr = newStr + c + "#";
    14     //回文半径记录数组
    15     int* rIndex = new int[newStr.length()];
    16     int c = -1;//回文中心
    17     int R = -1;//回文右边界 R位于回文对称右边界的右边一个字母
    18     int maxL = INT_MIN;//记录最长回文字长
    19     for (int i = 0; i < newStr.length(); ++i)
    20     {
    21         //第一步直接取得可能的最短的回文半径，当i>R时，最短的回文半径是1，
    22         //反之，最短的回文半径可能是i对应的i'的回文半径或者i到R的距离
    23         if (R > i)
    24             rIndex[i] = rIndex[2 * c - i] < R - i ? rIndex[2 * c - i] : R - i;
    25         else
    26             rIndex[i] = 1;
    27         //取最小值后开始从边界暴力匹配，匹配失败就直接退出
    28         while (i + rIndex[i] < newStr.length() && i - rIndex[i] > -1)
    29         {
    30             if (newStr[i + rIndex[i]] == newStr[i - rIndex[i]])//向两边扩展，找回文字母
    31                 rIndex[i]++;
    32             else
    33                 break;
    34         }
    35         //观察此时R和C是否能够更新
    36         if (i + rIndex[i] > R)
    37         {
    38             R = i + rIndex[i];
    39             c = i;
    40         }
    41         //更新最大回文半径的值
    42         maxL = maxL > rIndex[i] ? maxL : rIndex[i];
    43     }
    44     delete[] rIndex;
    45     //这里解释一下为什么返回值是maxn-1，因为manacherstring的长度和原字符串不同，
    46     //所以这里得到的最大回文半径其实是原字符串的最大回文子串长度加1，
    47     //有兴趣的可以自己验证试试,-1是为了将后面的‘#’去掉
    48     return maxL - 1;    
    49     
    50 }
    51 
    52 void Test()
    53 {
    54     string str = "abc1234321ab";
    55     cout << Manacher(str) << endl;
    56 }

转载于:https://www.cnblogs.com/zzw1024/p/11031706.html