LeetCode-5 Longest Palindromic Substring

Description

求最长回文串。

Constraints

字符串长度不超过\(1000\)。

Solution

市面上解法很多了，这里展示\(O(n)\)的回文自动机（回文树）。

虽然我在很早以前还写过教程，但其实也忘得差不多了……

Code

struct PT {
    const std::string &str;
    vector<array<int, 127>> trans;
    vector<int> fail;
    vector<int> len;
    int odd, even;
    int last;
    struct {
        int index;
        int len;
    } best;

    int make(int f, int l) {
        int node = trans.size();
        trans.push_back({});
        fail.emplace_back(f);
        len.emplace_back(l);
        return node;
    }

    PT(const std::string &str)
        : str(str),
          odd(make(0, -1)),
          even(make(0, 0)),
          last(even),
          best{}
    {
        for(int i = 0; i < str.size(); ++i) {
            add(i);
        }
    }

    void add(int index) {
        int c = str[index];
        int u = last;
        int v = failwalk(u, index);
        if(!trans[v][c]) {
            int f, l;
            if(len[v] == -1) {
                f = even;
                l = 1;
            } else {
                // Note:
                int w = failwalk(fail[v], index);
                f = trans[w][c];
                l = len[v] + 2;
            }
            int n = make(f, l);
            trans[v][c] = n;
        }
        last = trans[v][c];
        if(len[last] > best.len) {
            // 注意这里`index`是后缀最后一个，`best.index`是前缀第一个
            best.index = index - len[last] + 1;
            best.len = len[last];
        }
    }

    int failwalk(int u, int index) {
        for(;;) {
            // cXc
            // ^ lo is here
            //   ^ index is here
            int lo = index - 1 - len[u];
            // c == c
            if(lo >= 0 && str[lo] == str[index]) break;
            // shrink X
            u = fail[u];
        }
        return u;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() <= 1) return s;
        PT pt(s);
        return s.substr(pt.best.index, pt.best.len);
    }
};

Link

LeetCode-5 Longest Palindromic Substring