0

## 【圖解演算法】【Hash】 LeetCode 459 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;
}

}
``````
1. 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"
...

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

3. assemble current substring hash into a whole-string hash

4. 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.