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;   
    }
    
    
}

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.