uopspop

Untitled

Nov 10th, 2020
512
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package other;
  2.  
  3. public class Hash_leetcode_459_repeatedsubstringpattern_hash_v2_nomodulo {
  4.     long magic_num = 31;
  5.  
  6.     public boolean repeatedSubstringPattern(String s) {
  7.         // only lowercase
  8.         // for - pick one substring
  9.         //  for - repeat and check
  10.         if (s.isEmpty()) return false;
  11.  
  12.         // get target hash
  13.         long target_hash = hash(s);
  14.  
  15.         Long now_hash = null;
  16.         int str_size = s.length();
  17.         for (int i = 0; i < str_size; i++) {
  18.             if (i >= str_size) break;
  19.             int substring_size = i + 1;
  20.  
  21.             // calculate hash
  22.             if (now_hash == null) {
  23.                 now_hash = hash(s.substring(0, 1));
  24.             }else {
  25.                 // ab -> ab_ move left
  26.                 now_hash *= magic_num;
  27.                 // ab_ + c
  28.                 now_hash += s.charAt(i);
  29.             }
  30.  
  31.             if (str_size % substring_size != 0 // must be a factor
  32.                     || str_size == substring_size) // must append at least once
  33.             {
  34.                 continue;
  35.             }
  36.  
  37.             // assemble as a whole string for compare
  38.             int chunk_num = str_size/substring_size;
  39.             long now_assembled_hash = now_hash;
  40.             for (int k = 1; k < chunk_num; k++) { // start from k = 1
  41.                 // abc -> abc___ move left
  42.                 for (int m = 0; m < substring_size; m++) {
  43.                     now_assembled_hash *= magic_num;
  44.                 }
  45.                 // abc___ + abc -> abcabc
  46.                 now_assembled_hash += now_hash;
  47.             }
  48.  
  49.             // check hash (beleive in god, believe in your hash function)
  50.             if (now_assembled_hash == target_hash) {
  51.                 return true;
  52.             }
  53.         }
  54.  
  55.         return false;
  56.  
  57.     }
  58.  
  59.  
  60.     private long hash(String s) {
  61.         long result = 0;
  62.  
  63.         for (int i = 0; i < s.length(); i++) {
  64.             result *= magic_num;
  65.             result += s.charAt(i);
  66.         }
  67.  
  68.         return result;
  69.     }
  70.  
  71. }
  72.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×