题解 | #牛群编号的回文顺序II# Manacher算法

知识点

Manacher算法

思路

很经典的求最长回文子串的问题，一般来说有三种办法

• 动态规划 时间复杂度
• 中心扩展 时间复杂度
• Manacher算法 时间复杂度

这道题的范围 显然不可以使用的算法，但是Manacher算法的难度远超面试难度。

以下代码为链表形式的Manacher算法。

时间复杂度

AC Code（C++）

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    int expand (const vector<ListNode*>& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left]->val == s[right]->val) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }
    ListNode* maxPalindrome(ListNode* head) {
        vector<ListNode*> s;
        auto p = head;
        while (p) {
            s.emplace_back(p);
            p = p->next;
        }
        int n = s.size();

        int start = 0, end = -1;
        vector<ListNode*> t = {new ListNode(-1)};
        for (auto x : s) {
            t.emplace_back(x);
            t.emplace_back(new ListNode(-1));
        }
        t.emplace_back(new ListNode(-1));
        s = t;

        vector<int> arm_len;
        int right = -1, j = -1;
        for (int i = 0; i < s.size(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = min(arm_len[i_sym], right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.push_back(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        vector<ListNode*> ans;
        for (int i = start; i <= end; ++i) {
            if (s[i]->val != -1) {
                ans.emplace_back(s[i]);
            }
        }
        if (ans.size() == n) return nullptr;
        ans.back()->next = nullptr;
        return ans.front();
    }
};