Advertisement
YEZAELP

PROG-1019: DNA

Jun 30th, 2020
111
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // PPPPPPP-PP  
  4. using lli = long long;
  5. using pii = pair <lli, int>;
  6. const lli PB = 98765431;
  7. const lli INF = 2e18;
  8.  
  9. string str[2];
  10. int found(set <lli> S1, set<lli> S2, vector<lli> pst){
  11.     for(auto s:S1){
  12.         if(S2.find(s) != S2.end()) {
  13.             for(int i=0; i<pst.size();i++){
  14.                 if(pst[i] == s) return i;
  15.             }
  16.         }
  17.     }
  18.     return -1;
  19. }
  20.  
  21. int hashing(int n){
  22.  
  23.     lli hsh[2] = {0}, rem = 1;
  24.     set <lli> S[2];
  25.     vector <lli> pst;
  26.     for(int i=0; i<n; i++){
  27.         if(i != 0) rem *= PB;
  28.         for(int j=0;j<2;j++) hsh[j] = hsh[j]*PB + str[j][i];
  29.     }
  30.     for(int j=0;j<2;j++){
  31.         for(int i=0; i<=str[j].size()-n; i++){
  32.             if(i != 0) hsh[j] = hsh[j]*PB + str[j][i+n-1];
  33.             if(j == 0) pst.push_back(hsh[j]);
  34.             S[j].insert(hsh[j]);
  35.             hsh[j] = hsh[j] - rem*str[j][i];
  36.         }
  37.     }
  38.  
  39.     return found(S[0],S[1],pst);
  40. }
  41.  
  42. int main(){
  43.  
  44.     cin>>str[0];
  45.     cin>>str[1];
  46.  
  47.     int sz = min(str[0].size(), str[1].size()), l=0, r=sz, mid, mx=0, pst;
  48.     while(l <= r){
  49.         mid = (l+r)/2;
  50.         int p = hashing(mid);
  51.         if(p != -1){
  52.             mx = max(mx, mid);
  53.             pst = p;
  54.             l = mid + 1;
  55.         }
  56.         else {
  57.             r = mid - 1;
  58.         }
  59.     }
  60.  
  61.     for(int i=pst; i<=pst+mx-1; i++) printf("%c",str[0][i]);
  62.  
  63.     return 0;
  64. }
Advertisement
RAW Paste Data Copied
Advertisement