Advertisement
YEZAELP

CUBE-191: Anagram

Aug 14th, 2020 (edited)
90
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const int N = 2e3 + 10;
  6. const lli PB = 98765431;
  7. const int AZ = 26 + 10;
  8. char A[N], B[N];
  9. lli cons[AZ];
  10. int la, lb;
  11.  
  12. int alph(int ch){
  13.     return ch - 'A' + 1;
  14.     /// A, ..., Z = 1, ..., 26
  15. }
  16.  
  17. bool check(int len){
  18.     unordered_set <lli> HSHA;
  19.     lli hshA = 0;
  20.     for(int i=0;i<len-1;i++)
  21.         hshA += cons[alph(A[i])];
  22.  
  23.     for(int i=len-1;i<la;i++){
  24.         hshA += cons[alph(A[i])];
  25.         HSHA.insert(hshA);
  26.         hshA -= cons[alph(A[i-len+1])];
  27.     }
  28.  
  29.     lli hshB = 0;
  30.     for(int i=0;i<len-1;i++)
  31.         hshB += cons[alph(B[i])];
  32.  
  33.     for(int i=len-1;i<lb;i++){
  34.         hshB += cons[alph(B[i])];
  35.         if(HSHA.find(hshB) != HSHA.end()) return true;
  36.         hshB -= cons[alph(B[i-len+1])];
  37.     }
  38.     return false;
  39. }
  40.  
  41. int main(){
  42.  
  43.     scanf("%s%s", &A, &B);
  44.  
  45.     la = strlen(A);
  46.     lb = strlen(B);
  47.  
  48.     cons[0] = 1;
  49.     for(int i=1;i<=AZ-10;i++){
  50.         cons[i] = (lli) cons[i-1] * PB;
  51.     }
  52.  
  53.     for(int len=min(la, lb);len>=0;len--){
  54.         if(check(len)){
  55.             printf("%d", len);
  56.             return 0;
  57.         }
  58.     }
  59.  
  60.     return 0;
  61. }
  62.  
  63. /*
  64. ABCDE
  65. DBAEC
  66. L = 3, 4 หาค่าไม่ได้
  67. L = 5    หาค่าได้
  68. */
Advertisement
RAW Paste Data Copied
Advertisement