题解：SP10570 LONGCS - Longest Common Substring

· · 题解

P5546 [POI 2000 R3] 公共串的加强版。

考虑二分其长度，我们可以枚举出所有此长度的子串，那么只要判断出是不是所有给出的串都含有一个子串即可，这一点可以哈希实现，由于时限较宽松可使用 map 存哈希值（单纯不想打别的）。

然后此题变得极为简单，我们成功使用哈希取代了后缀数组 AC 了此题（实则还在 waiting。。。

具体讲解一下：我们使用进制哈希，取一个质数 b 作为基数并用另外一个质数作为模数，然后将字符串看做数字得到其哈希值，那么求 [l, r] 的子串也是简单的（记 h_i 表示前 i 位的哈希值），计算 h_r - h_{l - 1} \cdot b ^ {r - l} \bmod p 即可。其中 b 的次幂可以预处理，总复杂度 O(T \sum |S| \log \sum |S|)。

:::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010, p = 1e9 + 7, base = 146131;
int t, n, b[N], slen[N];
string s;
vector<int> a[N];
map<int, int> mp, iop;
signed main(){
    cin >> t, b[0] = 1;
    for (int i = 1; i < N; i ++) 
        b[i] = b[i - 1] * base % p;
    while (t -- && cin >> n){
        for (int i = 1; i <= n; i ++){
            a[i].clear(), cin >> s,
            slen[i] = s.size(), a[i].push_back(0);
            for (int j = 1; j <= slen[i]; j ++)
                a[i].push_back((a[i][j - 1] * base + s[j - 1]) % p);
        }int l = 1, r = N, ans = 0;
        while (l <= r){
            mp.clear();
            bool flag = 0;
            int mid = (l + r) >> 1;
            for (int k = 1; k <= n; k ++){
                iop.clear();
                int lenk = slen[k];
                if (lenk < mid)continue;
                for (int i = 1; i <= lenk - mid + 1; i ++){
                    int op = (a[k][i + mid - 1] - a[k][i - 1] * b[mid] % p + p) % p;
                    if (!iop[op])mp[op] ++, iop[op] ++;
                    if (mp[op] == n){flag = 1;break;}
                }
            }if (flag)l = mid + 1, ans = mid;
            else r = mid - 1;
        }cout << ans << '\n';
    }return 0;
}

::: 本人第一篇题解，看懂了留个赞吧 QWQ。