题目描述：
给你n个字符串， 任选两个拼接在一起， 求可能的最大回文长度
（1）不可以自己拼自己
（2）n <= 1e5, 字符串总长度 <= 5e5
（3） 如果不存在答案，输出0

写法一：
字符串哈希 + map

X + Y 为回文串
预处理：
当我们在遍历每一个字符串的时候
它都可以作为 X 或者 Y
接下来我们在遍历该字符串的每一个元素的时候
进行分类讨论！！！

分别是作为 i <= len / 2 的时候：
这个时候是去找其他字符串作为左串
以第 i 个 元素 为中心 ： 构成奇数回文串
（1）先判断自己本身是否满足条件
（2）在所有其他串中找是否还有满足条件的字符串
以第 i 个 元素 为边界 ： 构成偶数回文串
（1）先判断自己本身是否满足条件
（2）在所有其他串中找是否还有满足条件的字符串

在这种情况下， 查找的字符串全是前缀串！！！

接着是 i >= len / 2的时候：
这个时候是去找其他字符串作为右串
以第 i 个 元素 为中心 ： 构成奇数回文串
（1）先判断自己本身是否满足条件
（2）在所有其他串中找是否还有满足条件的字符串
以第 i 个 元素 为边界 ： 构成偶数回文串
（1）先判断自己本身是否满足条件
（2）在所有其他串中找是否还有满足条件的字符串

在这种情况下， 查找的字符串全是后缀串！！！

！！！记住，为了避免自己与自己拼接，
每次现将自身 - 1, 遍历完后再 + 1

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
const int P = 131;
typedef unsigned long long ull;

typedef pair<ull, int> ULL;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    vector<string> s(n);
    vector<vector<ull>> f1(n), f2(n); 
    for(int i = 0; i < n; ++ i) cin >> s[i];

    int ma = 0;
    for(int i = 0; i < n; ++ i) {
        int len = s[i].size();
        f1[i].assign(len + 2, 0);
        f2[i].assign(len + 2, 0);
        ma = max(len, ma);
        for(int j = 1; j <= len; ++ j) {
            f1[i][j] = f1[i][j - 1] * P + s[i][j - 1] - 'a' + 1;
            int t = len - j + 1;
            f2[i][t] = f2[i][t + 1] * P + s[i][t - 1] - 'a' + 1; 
        //  cout << j << " " << f1[i][j] << " " << f2[i][t] << "\n";
        }
    }

    vector<ull> p(ma + 1, 0);
    p[0] = 1;
    for(int i = 1; i <= ma; ++ i) p[i] = p[i - 1] * P;

    int ans = 0;

    map<ULL, int> m1, m2;

    for(int i = 0; i < n; ++ i) {
        ull t = f2[i][1];
        int m = s[i].size();
        m1[{t, m}] ++;
        t = f1[i][m];
        m2[{t, m}] ++;  
    } 

    for(int i = 0; i < n; ++ i) {
        int m = s[i].size();
        m1[{f2[i][1], m}] --;
        m2[{f1[i][m], m}] --;
        for(int j = 1; j <= m; ++ j) {
            if(j - 1 < m - j) {
                if(f1[i][j - 1] == f2[i][j + 1] - f2[i][2 * j] * p[j - 1] || j == 1) {
                    ull t = f2[i][2 * j];
                    if(m2[{t, m - 2 * j + 1}]) ans = max(ans, 2 * m - 2 * j + 1);
                }
            }
            if(j < m - j) {
                if(f1[i][j] == f2[i][j + 1] - f2[i][2 * j + 1] * p[j]) {
                    ull t = f2[i][2 * j + 1];
                    if(m2[{t, m - 2 * j}]) ans = max(ans, 2 * m - 2 * j);
                }
            }

            if(j - 1 > m - j) {
                if(f2[i][j + 1] == f1[i][j - 1] - f1[i][2 * j - m - 1] * p[m - j] || j == m) {
                    ull t = f1[i][2 * j - m - 1];
                    if(m1[{t, 2 * j - m - 1}]) ans = max(ans, 2 * j - 1);
                }
            }
            if(j > m - j) {
                if(f2[i][j + 1] == f1[i][j] - f1[i][2 * j - m] * p[m - j]) {
                    ull t = f1[i][2 * j - m];
                    if(m1[{t, 2 * j - m}]) ans = max(ans, 2 * j);
                }
            }
        }
        m1[{f2[i][1], m}] ++;
        m2[{f1[i][m], m}] ++;
     }

     cout << ans << "\n";

    return 0;
}

写法二：
tire + manacher

X + Y 为回文串
当我们在遍历每一个字符串的时候
它都可以作为 X 或者 Y， 所以我假设当前遍历串为Y

当 X < Y：
我们会发现Y的前缀必然为回文串，接下我们在所有字符串中查找
是否有 Y 的后缀的逆串
以Y的第k个元素为例， 那么 Y：0 ~ k 为回文
Y： k + 1 ~ end 的逆串可以在其他字符串中找到
当 X >= Y：
我们会发现X的后缀必然为回文串，接下我们在所有字符串中查找
是否有 X 的前缀的逆串
以X的第k个元素为例， 那么 Y：k ~ end 为回文
Y： 0 ~ k - 1 的逆串可以在其他字符串中找到

所以：
我们现在将每个字符串的逆都预处理出来
再将每个字符串跑一遍manacher，
这样的话对于任意一个字符串的区间 [l, r]
我们都可以O(1)的时间来判断是否回文

我们在
insert()
用suf[p] : 记录当前位置后的最大回文长度
将前缀字符串放入trie树中

在query()
因为我们处理的是逆串
对于 X < Y ：
走到第k个位置：
如果发现从 第k + 1个位置到最后为回文串， 且在trie树中也能找到 第 0 ~ k 个元素的字符串，那说明可以构成
对于 X >= Y：
这个时候我们就会发现此时整个串都会被放入，
那么如果在trie树中可以找到 Y，且接下来的正序字符串还包含着回文后缀，
说明也能构成

在所有情况中取最大值！！！
！！！记住不能自己拼自己，所以当 s == reverse(s) 的时候
要去判断是否存在两个及以上，否则就是自己拼自己

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    vector<string> s(2 * n);

    int sum = 0, ans = 0;

    for(int i = 0; i < n; ++ i) cin >> s[i], sum += s[i].size();

    for(int i = n; i < 2 * n; ++ i) {
        s[i] = s[i - n];
        reverse(s[i].begin(), s[i].end());
    }

    vector<vector<int>> p(2 * n);

    auto get = [&](string s) -> vector<int> {
         string t;
         t = "$#";

         for(char c : s) t += c, t += '#';
         t += '^';

         int n1 = t.size();
         vector<int> p(n1 + 1);

         int mr = 0, mid = 0;
         for(int i = 1; i < n1; ++ i) {
            if(i < mr) p[i] = min(p[2 * mid - i], mr - i);
            else p[i] = 1;
            while(t[i - p[i]] == t[i + p[i]]) ++ p[i];
            if(i + p[i] > mr) {
                mr = i + p[i];
                mid = i;
             }
         }
         return p;
    }; 

    vector<vector<int>> ed(sum + 1);
    vector<vector<int>> son(sum + 1, vector<int>(26, 0));
    vector<int> cnt(sum + 1, 0), suf(sum + 1, 0);
    int id = 0;

    auto check = [&](int idx, int l, int r) -> bool {
        int t1 = 2 * l + 2, t2 = 2 * r + 2;
        int mid = t1 + t2 >> 1;
        int len = p[idx][mid];
        if(2 * len - 1 >= t2 - t1 + 1) return true;
        return false;
    };

    auto insert = [&](string s, int idx) -> void {
        int p = 0;
        int m = s.size();
        for(int i = 0; i < m; ++ i) {
            int u = s[i] - 'a';
            if(!son[p][u]) son[p][u] = ++ id;
            p = son[p][u];

            if(i < m - 1 && check(idx, i, m - 1)) suf[u] = max(suf[u], m - i);

        }
        cnt[p] ++;
    };

    auto query = [&](string s, int idx) -> void {
        int m = s.size();
        int p = 0;
    //  cout << m << "\n";
        for(int i = 0; i < m; ++ i) {
            int u = s[i] - 'a';
            if(!son[p][u]) return;
            p = son[p][u];
            if(i + 1 <= m - 1 && i < m - 1 && check(idx, i + 1, m - 1) && cnt[p]) ans = max(ans, m + i + 1);
        }

        string t = s;
        reverse(t.begin(), t.end());
        if(t != s) {
            if(cnt[p]) ans = max(ans, 2 * m + suf[p]);
        }
        else {
            if(cnt[p] > 1) ans = max(ans, 2 * m + suf[p]);
        }

    };

    for(int i = 0; i < n; ++ i) {
        p[i] = get(s[i]);
        insert(s[i], i);
    }

    for(int i = n; i < 2 * n; ++ i) p[i] = get(s[i]);

    for(int i = n; i < 2 * n; ++ i) {
          query(s[i], i);
     }

     cout << ans << "\n";

    return 0;
}