package other;

public class Hash_leetcode_459_repeatedsubstringpattern_hash_v2_nomodulo {
    long magic_num = 31;

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

        Long now_hash = null;
        int str_size = s.length();
        for (int i = 0; i < str_size; i++) {
            if (i >= str_size) break;
            int substring_size = i + 1;

            // calculate hash
            if (now_hash == null) {
                now_hash = hash(s.substring(0, 1));
            }else {
                // ab -> ab_ move left
                now_hash *= magic_num;
                // ab_ + c
                now_hash += s.charAt(i);
            }

            if (str_size % substring_size != 0 // must be a factor
                    || str_size == substring_size) // must append at least once
            {
                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;
                }
                // abc___ + abc -> abcabc
                now_assembled_hash += now_hash;
            }

            // check hash (beleive in god, believe in your hash function)
            if (now_assembled_hash == target_hash) {
                return true;
            }
        }

        return false;

    }


    private long hash(String s) {
        long result = 0;

        for (int i = 0; i < s.length(); i++) {
            result *= magic_num;
            result += s.charAt(i);
        }

        return result;
    }

}