Solution

• 首先，公共子串的长度一定小于等于最短串长minl，于是我们利用二分法在[0,minl]的区间内搜索可能的公共子串长度。

• 在每一次搜索中，我们利用哈希表记录所有长度为mid的子串在各串中是否出现（利用二进制掩码代替集合）。若某一子串满足在所有串中均出现（掩码全1），则更新搜索左边界为mid，否则更新搜索右边界为mid-1。

Complexity

时间复杂度

设平均串长为m，二分搜索共需要log(m)次,总时间O(mnlog(m))

空间复杂度

建立hash表需要O(m^2n)

Code

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n;
    cin>>n;
    vector<string>strs;

    int minl=0x7fffffff;
    for(int i=0;i<n;i++){
        string str;
        cin>>str;
        strs.push_back(str);
        int s=str.size();
        minl=min(minl,s);//找到最短串长
    }

    int l=0,r=minl;

    while(l<r){

        int mid=(l+r)/2+1;//二分法搜索最大公共串长

        unordered_map<string,char>Hash;
        int mask=0;
        bool valid=false;

        for(int i=1;i<=n;i++){
            string str=strs[i-1];
            mask|=(1<<i);//全匹配掩码
            int s=str.size();
            for(int a=0;a<s-mid+1;a++){
                string sub=str.substr(a,mid);
                Hash[sub]|=(1<<i);//标记
                if(Hash[sub]<mask)Hash.erase(sub);//删除无效值
                if(i==n&&Hash[sub]==mask){
                    valid=true;//找到长为mid的公共串
                    break;
                }
            }
        }

        if(valid)l=mid;
        else r=mid-1;

    }

    cout<<l<<endl;
    return 0;
}