1 #include 
     
       2 #include 
      
        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         else26             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             else33                 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 }