d.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

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

using namespace std;
const int INF = 1e9 + 1;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int MAXN = 1e4 + 10;
int p1 = 31;
int p2 = 37, n;
ll hash1[12][MAXN], hash2[12][MAXN], st1[MAXN], st2[MAXN], len[12];
string s[12];

set <pair <ll, ll> > set_hashs;
map <pair <ll, ll>, int > cnt_hashs;

pair <ll, ll> best_hash = {-1LL, -1LL};

pair <ll, ll> get_hash(int i, int l, int r){
    ll h1 = (hash1[i][r] - hash1[i][l - 1] + MOD1) * st1[10000 - l] % MOD1;
    ll h2 = (hash2[i][r] - hash2[i][l - 1] + MOD2) * st2[10000 - l] % MOD2;
    return {h1, h2};
}
bool check(int d){
    cnt_hashs.clear();
    for (int i = 1; i <= n; i++){
        set_hashs.clear();
        for (int j = d; j <= len[i]; j++){
            set_hashs.insert(get_hash(i, j - d + 1, j));
        }
        for (auto z : set_hashs){
            cnt_hashs[z]++;
            if (cnt_hashs[z] == n){
                best_hash = z;
                return true;
            }
        }
    }
    return false;
}

void solve(){
    cin >> n;
    int l = 1;
    int r = 10000;
    for (int i = 1; i <= n; i++){
        cin >> s[i];
        r = min(r, int(s[i].size()));
    }
    st1[0] = st2[0] = 1;
    for (int i = 1; i <= 10000; i++){
        st1[i] = st1[i - 1] * p1 % MOD1;
        st2[i] = st2[i - 1] * p2 % MOD2;
    }
    for (int i = 1; i <= n; i++){
        len[i] = s[i].size();
        s[i] = "#" + s[i];
        for (int j = 1; j <= len[i]; j++){
            hash1[i][j] = (hash1[i][j - 1] + (s[i][j] - 'a' + 1) * st1[j]) % MOD1;
            hash2[i][j] = (hash2[i][j - 1] + (s[i][j] - 'a' + 1) * st2[j]) % MOD2;
        }
    }

    int ans = 0;

    while (l <= r){
        int mid = (l + r) / 2;
        if (check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }

    check(ans);
    for (int j = ans; j <= len[1]; j++){
        if (get_hash(1, j - ans + 1, j) == best_hash){
            cout << s[1].substr(j - ans + 1, ans);
            return;
        }
    }
    cout << ans;

}

int main() {
    IOS;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}