SHARE
TWEET

Untitled

a guest May 19th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define pb push_back
  6. #define all(a) a.begin(), a.end()
  7. #define rall(a) a.rbegin(), a.rend()
  8.  
  9. void out(vector<int> a) {
  10.     for (auto it = a.begin(); it != a.end(); ++it) cout << (*it) << " ";
  11.     cout << "\n";
  12. }
  13.  
  14. int n, m;
  15. string s, t;
  16. int sz;
  17. const int b = 5, mod = 1354828, mod2 = mod * mod;
  18. vector<int> power;
  19. vector<int> hash1, hash2;
  20.  
  21. inline void read() {
  22.     cin >> n >> m >> s >> t;
  23.     sz = max(n, m);
  24.     power.resize(sz + 1);
  25.     hash1.resize(sz + 1);
  26.     hash2.resize(sz + 1);
  27. }
  28.  
  29. int trans(char c) {
  30.     if (c == 'A') return 1;
  31.     if (c == 'C') return 2;
  32.     if (c == 'G') return 3;
  33.     if (c == 'T') return 4;
  34. }
  35.  
  36. void calc_power() {
  37.     power[0] = 1;
  38.     for (int i = 1; i <= sz; ++i)
  39.         power[i] = (power[i-1] * b) % mod;
  40. }
  41.  
  42. void calc_hash(vector<int> &h, string &str) {
  43.     h[0] = trans(str[0]);
  44.     for (int i = 1; i < str.size(); ++i) {
  45.         int c = trans(str[i]);
  46.         h[i] = (h[i - 1] * b + c) % mod;
  47.     }
  48. }
  49.  
  50. int get_hash(vector<int> &h, int l, int r) {
  51.     if (l == 0) return h[r];
  52.     else return ((mod2 + h[r] - (h[l-1] * power[r-l+1] % mod))+ mod) % mod;
  53. }
  54.  
  55. bool used[mod];
  56.  
  57. bool f(int mid) {
  58.     memset(used, false, sizeof(used));
  59.     int cnt = 0;
  60.     for (int i = 0; i <= n - mid; ++i) {
  61.         int id = get_hash(hash1, i, i + mid - 1);
  62.         if (!used[id]) ++cnt;
  63.         used[id] = true;
  64.     }
  65.     for (int i = 0; i <= m - mid; ++i) {
  66.         int id = get_hash(hash2, i, i + mid - 1);
  67.         if (used[id]) --cnt;
  68.         used[id] = false;
  69.     }
  70.     if (cnt == 0) return true;
  71.     else return false;
  72. }
  73.  
  74. string res(int k) {
  75.     memset(used, false, sizeof(used));
  76.     for (int i = 0; i <= m - k; ++i) {
  77.         int id = get_hash(hash2, i, i + k - 1);
  78.         used[id] = true;
  79.     }
  80.     for (int i = 0; i <= n - k; ++i) {
  81.         int id = get_hash(hash1, i, i + k - 1);
  82.         if (!used[id]) return s.substr(i, k);
  83.     }
  84. }
  85.  
  86. vector<string> ans;
  87.  
  88. inline void solve() {
  89.     calc_power();
  90.     calc_hash(hash1, s);
  91.     calc_hash(hash2, t);
  92.  
  93.     int l = 1, r = min(n, m) + 1;
  94.     for (int i = 0; i<20; ++i) {
  95.         int mid  = (l + r) / 2;
  96.         if (f(mid)) l = mid + 1;
  97.         else r = mid;
  98.     }
  99.     if (r == min(n, m) + 1) {
  100.         if (n > m) cout << s.substr(0, m+1);
  101.         else cout << "NONE";
  102.     }
  103.     else cout << res(r);
  104. }
  105.  
  106. signed main() {
  107. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  108. cout << fixed << setprecision(20);
  109. //freopen("input.txt", "r", stdin);
  110. //freopen("output.txt", "w", stdout);
  111.     read();
  112.     solve();
  113. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top