solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

char s[5000 * 2 + 10];
struct Manacher {
    vector<int> Mp;
    Manacher(string &_s) {
        init(_s);
    }

    void init(string &_s) {
        int scnt = 0;
        int n = _s.size();
        s[scnt++] = '$';
        s[scnt++] = '#';
        for (int i = 0; i < n; i++) {
            s[scnt++] = _s[i];
            s[scnt++] = '#';
        }
        s[scnt++] = '?';
        int id = 0, mx = 0;
        int l = scnt;
        Mp.resize(l);
        for (int i = 0; i < l - 1; i++) {
            Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
            while (i + Mp[i] < l && i - Mp[i] >= 0 && s[i + Mp[i]] == s[i - Mp[i]]) Mp[i]++;
            if (i + Mp[i] > mx) {
                mx = i + Mp[i];
                id = i;
            }
        }
    }

    Manacher() {}

    int query(int l, int r) {
        // l = r 那么就表示以 l 为中心的最长回文串
        // l + 1 = r 那么就表示以 l 和 r 中间为中心的最长回文串
        // 返回长度, 如 "aabaa", l = r = 2, 即以 b 位中心的回文串长度，返回 3. 如 "abba", l = 1, r = 2, 返回 2
        int idx = (l + 1) * 2;
        if (l != r) {
            idx++;
        }
        int length = Mp[idx];
        return length / 2;
    }
};

struct TrieNode {
    int nxt[26];
    vector<int> finish;
    vector<int> have;
    TrieNode() {
    }
    TrieNode(int char_size) {
        memset(nxt, -1, sizeof(nxt));
    }
    // 一些 hook 函数，用于 Trie 算法以及 ac 自动机, 可以覆盖这些函数来实现一些功能

    // 当加入到字典树后，对最终的节点(当前节点)进行一些操作
    void update_when_finish_in_trie(int idx) {
        finish.push_back(idx);
    };

    // 当加入到字典树时，根据当前节点和子节点的信息，对当前节点进行一些操作
    void update_when_push_in_trie(TrieNode &child_node){};

    // 当构建 fail 函数时，根据当前节点和 fail 节点的信息，对当前节点进行一些操作
    void update_when_build_fail(TrieNode &fail_node){};

    void clear(int char_size) {
        memset(nxt, -1, sizeof(nxt));
        for (int i = 0; i < char_size; i++) nxt[i] = -1;
        finish.clear();
        have.clear();
    }
};

const int maxn = 5000 * 300 + 1;
TrieNode nodes1[maxn], nodes2[maxn];

unordered_set<int> S;

struct Trie {
   public:
    int root;
    int ncnt;
    int char_size;
    int margin;
    TrieNode *nodes;

    int new_node() {
        nodes[ncnt].clear(char_size);
        return ncnt++;
    }

    Trie(int char_size, int margin, TrieNode *n) : root(0), char_size(char_size), margin(margin) {
        ncnt = 0;
        nodes = n;
        new_node();
    }

    void add(const string &s, int s_idx, int node_idx, int idx) {
        /*
         * 将字符串 s 的 s_idx 位置开始的后缀加入到字典树中. node_idx 为当前节点的下标
         */
        if (S.count(s_idx)) {
            nodes[node_idx].have.push_back(idx);
        }
        if (s_idx == s.size()) {
            // 完成加入
            nodes[node_idx].update_when_finish_in_trie(idx);
        } else {
            const int c = s[s_idx] - margin;
            if (nodes[node_idx].nxt[c] == -1) {
                nodes[node_idx].nxt[c] = new_node();
            }
            add(s, s_idx + 1, nodes[node_idx].nxt[c], idx);
            // 根据当前节点的子节点更新当前节点
            nodes[node_idx].update_when_push_in_trie(nodes[nodes[node_idx].nxt[c]]);
        }
    }

    void add(const string &s, int idx) {
        add(s, 0, root, idx);
    }

    int go(int now, char it) {
        int c = it - margin;
        int go = nodes[now].nxt[c];
        return go;
    }
};

Manacher m1[5005];
class Solution {
   public:
    vector<vector<int>> palindromePairs(vector<string> &words) {
        int n = words.size();
        Trie trie(26, 'a', nodes1), trie2(26, 'a', nodes2);
        S.clear();
        for (int i = 0; i < n; i++) {
            if (words[i].size() > 0) {
                S.insert(words[i].size());
            }
        }
        vector<int> empty;
        for (int i = 0; i < n; i++) {
            string s = words[i];
            if (s == "") {
                empty.push_back(i);
                continue;
            }
            trie.add(s, i);
            m1[i].init(s);
            reverse(s.begin(), s.end());
            trie2.add(s, i);
        }
        auto check = [&](Manacher &ma, int l, int r) -> bool {
            if (l > r) return true;
            return ma.query((l + r) / 2, (l + r + 1) / 2) * 2 - (r - l + 1) % 2 >= r - l + 1;
        };
        vector<vector<int>> ans;

        int now1 = trie.root, now2 = trie2.root;

        function<void(int, int, int)> dfs = [&](int now1, int now2, int len) {
            if (trie.nodes[now1].finish.size() > 0) {
                auto &v1 = trie.nodes[now1].finish;
                auto &v2 = trie2.nodes[now2].have;
                for (auto it1 : v1) {
                    for (auto it2 : v2) {
                        if (it1 == it2) continue;
                        string &s = words[it2];
                        int sz = s.size();
                        if (check(m1[it2], 0, sz - len - 1)) {
                            ans.push_back({it1, it2});
                        }
                    }
                }
            }

            if (trie2.nodes[now2].finish.size() > 0) {
                auto &v1 = trie2.nodes[now2].finish;
                auto &v2 = trie.nodes[now1].have;
                for (auto it1 : v1) {
                    for (auto it2 : v2) {
                        if (it1 == it2) continue;
                        string &s = words[it2];
                        int sz = s.size();
                        if (sz != len && check(m1[it2], len, sz - 1)) {
                            ans.push_back({it2, it1});
                        }
                    }
                }
            }

            for (int i = 0; i < 26; i++) {
                int go1 = trie.go(now1, 'a' + i);
                int go2 = trie2.go(now2, 'a' + i);
                if (go1 != -1 && go2 != -1) {
                    dfs(go1, go2, len + 1);
                }
            }
        };
        dfs(now1, now2, 0);
        debug(ans);

        if (empty.size() > 0) {
            for (int i = 0; i < n; i++) {
                int sz = words[i].size();
                if (sz == 0) continue;
                if (check(m1[i], 0, sz - 1)) {
                    for (auto it : empty) {
                        ans.push_back({i, it});
                        ans.push_back({it, i});
                    }
                }
            }

            for (int i = 0; i < empty.size(); i++) {
                for (int j = i + 1; j < empty.size(); j++) {
                    ans.push_back({empty[i], empty[j]});
                    ans.push_back({empty[j], empty[i]});
                }
            }
        }

        return ans;
    }
};