Guest User

Untitled

a guest
Jan 16th, 2014
430
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <string>
  3. #include <set>
  4. #include <map>
  5. #include <cstdlib>
  6. using namespace std;
  7.  
  8. #define mp make_pair
  9. typedef long long LL;
  10.  
  11. const int N = 1000;
  12. const int B = 33;
  13. const int M1 = 1000000007;
  14. const int M2 = 1000000021;
  15. const int M3 = 1000000033;
  16. const int LIMIT = 1000000000;
  17.  
  18. char in[N];
  19. int len;
  20.  
  21. int get(int mod, int base)
  22. {
  23.     LL p = 1, h = 0;
  24.     for (int i = len-1; i >= 0; --i)
  25.     {
  26.         h += p*(in[i]-'A'+1)%mod;
  27.         p = (p*base)%mod;
  28.     }
  29.     return h;
  30. }
  31.  
  32. set<pair<int, int> > hashes;
  33. set<string> strs;
  34.  
  35. bool generate()
  36. {
  37.     len = 16;
  38.     for (int i = 0; i < len; ++i)
  39.         in[i] = 'A'+rand()%26;
  40.     in[len] = 0;
  41.     if (strs.count(in))
  42.     {
  43.         printf("safe colision\n");
  44.         return true;
  45.     }
  46.     strs.insert(in);
  47.     pair<int, int> p = mp(get(M1, B), get(M2, B));
  48.     if (hashes.count(p))
  49.     {
  50.         printf("%s\n", in);
  51.         return false;
  52.     }
  53.     hashes.insert(p);
  54.     if (hashes.size() == LIMIT) return false;
  55.     return true;
  56. }
  57.  
  58. int main()
  59. {
  60.     srand(time(NULL));
  61.     while (generate());
  62.     printf("%d\n", (int) hashes.size());
  63. }
RAW Paste Data