mickypinata

KOI: Interval

Dec 6th, 2021
676
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. typedef long long lli;
  5.  
  6. const int B = 1e9 + 7;
  7. const int L = 1500;
  8.  
  9. lli enc[26];
  10. char strA[L], strB[L];
  11.  
  12. int main(){
  13.  
  14.     enc[0] = 1;
  15.     for(int i = 1; i < 26; ++i){
  16.         enc[i] = enc[i - 1] * B;
  17.     }
  18.     scanf(" %s %s", strA + 1, strB + 1);
  19.     int lenA = strlen(strA + 1);
  20.     int lenB = strlen(strB + 1);
  21.     int len = min(lenA, lenB);
  22.     for(int i = len; i >= 1; --i){
  23.         lli hsh = 0;
  24.         set<lli> stt;
  25.         for(int j = 1; j <= i; ++j){
  26.             hsh += enc[strA[j] - 'a'];
  27.         }
  28.         stt.insert(hsh);
  29.         for(int j = i + 1; j <= lenA; ++j){
  30.             hsh -= enc[strA[j - i] - 'a'];
  31.             hsh += enc[strA[j] - 'a'];
  32.             stt.insert(hsh);
  33.         }
  34.         hsh = 0;
  35.         for(int j = 1; j <= i; ++j){
  36.             hsh += enc[strB[j] - 'a'];
  37.         }
  38.         if(stt.find(hsh) != stt.end()){
  39.             cout << i;
  40.             return 0;
  41.         }
  42.         for(int j = i + 1; j <= lenB; ++j){
  43.             hsh -= enc[strB[j - i] - 'a'];
  44.             hsh += enc[strB[j] - 'a'];
  45.             if(stt.find(hsh) != stt.end()){
  46.                 cout << i;
  47.                 return 0;
  48.             }
  49.         }
  50.     }
  51.     cout << '0';
  52.  
  53.     return 0;
  54. }
  55.  
RAW Paste Data