Manacher算法求最大回文串

Manacher 算法是用来求最长回文子串的算法
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        string s = "$#";
        for (const char& ch : A)
        {
            s += ch;
            s += '#';
        }
        int len = s.size();
        s += '!';
        int imax = 0;
        int rmax = 0;
        vector<int> f(len);
        for (int i = 1; i < len; ++i)
        {
            //初始化
            f[i] = (i <= rmax) ? min(rmax - i + 1, f[2 * imax - i]) : 1;
            //中心扩展
            while (s[i + f[i]] == s[i - f[i]]) ++f[i];
            //更新
            if (f[i] > rmax - imax + 1)
            {
                imax = i;
                rmax = i + f[i] - 1;
            }
        }

        return f[imax]-1;  //最长回文子串长度
    }
};

void Manacher(string s) 
    {
        //改造原字符串，如：asa变成$#a#s#a#!，assa变成$#a#s#s#a#!
        string t = "$#";
        for (const char &c : s) {
            t += c;
            t += '#';
        }
        int len = t.length(); 
        t += '!';
        auto f = vector<int>(len); 
        //对于第一个$和最后一个！，可以不计算以其为中心的最大回文子串 
        int iMax = 0;  //最大回文子串回文中心 
        int rMax = 0;  //最大回文子串右端点  

        for (int i = 1; i < len; ++i)  //计算以i为中心的最大回文子串 
        {
            // 初始化 f[i]：以i为中心的最大回文子串半径，i点也包括在内
            //f[2 * iMax - i] = f[iMax - (i - iMax)] = f[i对位]，如果对位的f[i]没有超出最大回文串边界(左边界)则f[i]=f[i对位]成立，如1234321倒数第二位的2的f[i]等于顺数第二位的2的f[i]
            //如果对位的f[i]超出了最大回文串边界（左边界），则本位的f[i]是从rMax-i+1开始中心增大的，如31234321倒数第二位的2的f[i]不等于顺数第第三位的2的f[i]，而是为rMax-i+1
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;  
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (f[i] > rMax - iMax + 1)  //更新最大回文子串及其右边界
            {
                iMax = i;
                rMax = i + f[i] - 1;
            }
//          if (i + f[i] - 1 > rMax)  //更新最右回文子串及其右边界，但它不一定是最长回文子串，求回文串数可用这个条件
//         {
//                iMax = i;
//                rMax = i + f[i] - 1;
//          }
//            ans += (f[i] / 2);
        }

        cout << f[iMax] - 1 << endl;  //这是最大回文串长度

//      for (int i = iMax - f[iMax] + 1; i <= rMax; ++i)  //这里输出最大回文串
//        {
//            if (t[i] != '#')
//            {
//                cout << t[i];
//            }
//        }
    }

例题：

/*
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
*/  
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';

        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }

        return ans;
    }
};