Advertisement
SuitNdtie

Anagram

May 10th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<set>
  4. using namespace std;
  5. typedef long long int ll;
  6.  
  7. ll const Pr = 98765431;
  8. int min(int a,int b){
  9.     return (a < b ? a : b);
  10. }
  11. int main()
  12. {
  13.     char str1[2010];
  14.     char str2[2010];
  15.    
  16.     ll value[30];
  17.     value[0] = Pr;
  18.     for(int i = 1 ; i <= 27 ; i ++){
  19.         value[i] = value[i-1] * Pr;
  20.     }
  21.     scanf("%s %s",str1,str2);
  22.     int len1 = strlen(str1);
  23.     int len2 = strlen(str2);
  24.     int minl = min(len1,len2);
  25.    
  26.     int ans = 0;
  27.     for(int size = 1 ; size <= minl ; size ++){
  28.         set<ll> table;table.clear();
  29.         ll hs = 0;
  30.         for(int i = 0 ; i < len1 ; i ++ ){
  31.             hs += value[str1[i] - 'A'];
  32.             if(i >= size - 1){
  33.             //  if(table.count(hs) == 0){
  34.                     table.insert(hs);
  35.             //  }
  36.                 hs -= value[str1[i-size+1]-'A'];
  37.             }
  38.         }
  39.         hs = 0;
  40.         for(int i = 0 ; i < len2 ; i++){
  41.             hs += value[str2[i]-'A'];
  42.             if(i >= size-1){
  43.                 if(table.count(hs) == 1){
  44.                     ans = size;
  45.                     break; 
  46.                 }
  47.                 hs -= value[str2[i-size+1]-'A'];
  48.             }
  49.         }
  50.     }
  51.     printf("%d",ans);
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement