【图解演算法】【Hash】 LeetCode 459 Repeated Substring Pattern

Question link: https://leetcode.com/problems/repeated-substring-pattern/

class Solution {        long magic_num = 31;     long mod_num = 1000000000 + 7;        public boolean repeatedSubstringPattern(String s) {        // only lowercase         // for - pick one substring        //  for - repeat and check         if (s.isEmpty()) return false;                        // get target hash         long target_hash = hash(s);                // initailization        Long now_hash = null;        int i = 0;                int str_size = s.length();        while (true) {            if (i >= str_size) break;             int substring_size = i + 1;                        // calculate hash             if (now_hash == null) {                now_hash = hash(s.substring(0, 1));                now_hash = mod(now_hash, mod_num);            }else {                // ab -> ab_ move left                 now_hash *= magic_num;                 now_hash = mod(now_hash, mod_num);                // ab_ + c                now_hash += s.charAt(i);                now_hash = mod(now_hash, mod_num);            }            System.out.println("i: " + i);            if (str_size % substring_size != 0 // must be a factor               || str_size == substring_size) // must append at least once             {                i++;                continue;            }                        // assemble as a whole string for compare            int chunk_num = str_size/substring_size;            long now_assembled_hash = now_hash;            for (int k = 1; k < chunk_num; k++) { // start from k = 1                // abc -> abc___ move left                for (int m = 0; m < substring_size; m++) {                    now_assembled_hash *= magic_num;                    now_assembled_hash = mod(now_assembled_hash, mod_num); // be very careful about overflow                 }                // abc___ + abc -> abcabc                now_assembled_hash = mod(now_assembled_hash, mod_num);                now_assembled_hash += now_hash;                now_assembled_hash = mod(now_assembled_hash, mod_num);            }            // check hash (belive in god, believe in your hash function)            System.out.println(chunk_num + "-" + now_assembled_hash + ":" + target_hash);            if (now_assembled_hash == target_hash) {                return true;            }                        i++;        }                return false;            }            private long hash(String s) {        long result = 0;                for (int i = 0; i < s.length(); i++) {            result *= magic_num;            result = mod(result, mod_num);            result += s.charAt(i);            result = mod(result, mod_num);        }                return result;            }        private long mod(long num, long mod){        return (num % mod + mod) % mod;       }        }

pick substring and calculate rolloing hash:
hash_val = 0
"a" = hash_val * magic_num + "a"
"ab" = hash_val * magic_num + "b"
"abc" = hash_val * magic_num + "c"
...

check if current substring is a factor of original string length
if (str_size % substring_size != 0)

assemble current substring hash into a whole-string hash

compare hash value
if (now_assembled_hash == target_hash) {
return true;
}

In the implementation, we leverage hash to avoid compare each substring one by one.
As a result, our time complexity is:

n * (chunk_num * (substring_size))

furthermore, when substring_size goes up, chunk_num goes down.
Therefore, roughly speaking, our time complexity will lean toward to original string length

n * str_size

At least, this is my thought. Let's discuss!

note: in this implementation, please be very careful about overflow while calculating hash value. really an evil in the detail.