P5546公共串

Hash + 二分 $O(n^2logn)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int P = 29, MOD = 1e9 + 7, N = 2005;
int n, l = 1, r = 2005, ans = 0;
int powP[N], a[6][N];
string s[6];
inline int cal(int x, int l, int r)
{
    return (a[x][r] - a[x][l - 1] * powP[r - l + 1] % MOD + MOD) % MOD;
}
inline bool check(int x)
{
    for (int i = 1; i + x - 1 <= s[1].size() - 1; i++) //枚举s[1]中每一个长度为x的字串
    {
        int now = cal(1, i, i + x - 1), cnt = 1;
        for (int j = 2; j <= n; j++) // 分别在其他单词中查找    
        {
            bool flag = false;
            for (int k = 1; k + x - 1 <= s[j].size() - 1; k++) // 枚举s[i]中每一个长度为x的字串
            {
                if (now == cal(j, k, k + x - 1))
                {
                    flag = true;
                    cnt++;
                    break;
                }
            }
            if (!flag)
                break;
        }
        if (cnt == n)
            return true;
    }
    return false;
}
inline void init(int x, int len)
{
    powP[0] = 1;
    for (int i = 1; i <= len; i++)
    {
        a[x][i] = (a[x][i - 1] * P + s[x][i] - 'a' + 1) % MOD;
        powP[i] = powP[i - 1] * P % MOD;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        int len = s[i].size();
        r = min(r, len);
        s[i] = "$" + s[i] + "^";
        init(i, len);
    }
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            l = mid + 1;
            ans = max(ans, mid);
        }
        else
            r = mid - 1;
    }
    cout << ans << endl;
}