fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long int;
  4. #define inf 1000000000000000LL
  5. #define mod 1000000007LL
  6. #define FOR(i,a,b) for(int i = a; i < b; i++)
  7. const ll Mod = 1000000009LL;
  8. const ll Base = 271LL;
  9.  
  10. struct hashed_string{
  11.     private:
  12.     string s; ll n;
  13.     vector <ll> prefix;
  14.     vector <ll> pow;
  15.     public:
  16.     hashed_string(string a){
  17.         s = a; n = a.size();
  18.         prefix.assign(n, 0);
  19.         ll sum = 0;
  20.         pow.assign(n+1, 0);
  21.         pow[0] = 1;
  22.         for (int i = 1; i <= n; i++){
  23.             pow[i] = (pow[i-1] * Base) % Mod;
  24.         }
  25.         for (int i = 0; i < n; i++){
  26.             prefix[i] = ((sum * Base) % Mod + s[i] - 'a' + 1) % Mod;
  27.             sum = prefix[i];
  28.         }
  29.     }
  30.     hashed_string(){}
  31.     ll get_hash(ll l, ll r){
  32.         ll x = prefix[r];
  33.         if (l >= 1){
  34.             l--;
  35.             x = ((x - prefix[l] * pow[r - l] % Mod) % Mod + Mod) % Mod;
  36.         }
  37.         return x;
  38.     }
  39. };
  40. void solve() {
  41.     ll n,m;
  42.     cin >> n >> m;
  43.     vector <string> l1( 2 * n);
  44.     for (int i = 0; i < 2 * n; i++) cin >> l1[i];
  45.     vector <hashed_string> v( 2 * n);
  46.     for (int i = 0; i < 2 * n; i++) v[i] = hashed_string(l1[i]);
  47.     auto flag = [&](ll length) -> bool{
  48.         for (int j = 0; j + length - 1 < m; j++){
  49.             set<ll> f1;
  50.             for (int i = 0; i < n; i++){
  51.                 f1.insert(v[i].get_hash(j, j + length - 1));
  52.             }
  53.             bool flag = true;
  54.             for (int i = n; i < 2 * n; i++){
  55.                 if (f1.find(v[i].get_hash(j, j + length - 1)) != f1.end()){
  56.                     flag = false;
  57.                     break;
  58.                 }
  59.             }
  60.             if (flag) return true; 
  61.         }
  62.         return false;
  63.     };
  64.     ll lo = 1;
  65.     ll hi = m;
  66.     while (lo != hi){
  67.         ll mid = (lo + hi) / 2;
  68.         if (flag(mid)){
  69.             hi = mid;
  70.         }  
  71.         else{
  72.             lo = mid + 1;
  73.         }
  74.     }
  75.     cout << lo << "\n";
  76. }
  77.  
  78. int main() {
  79.     freopen("cownomics.in","r",stdin);
  80.     freopen("cownomics.out","w",stdout);
  81.     ios::sync_with_stdio(false);
  82.     cin.tie(nullptr);
  83.  
  84.     ll t = 1;
  85.     while (t--) {
  86.         solve();
  87.     }
  88.  
  89.     return 0;
  90. }
Time limit exceeded #stdin #stdout 5s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GP0HH5
language:
C++14 (clang 8.0)
created:
2 hours ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!