// main concept: convert substring into a num, so we can calculate each round without inner loop
//
// what I learned:
// * leverage hash function (magicNum = 31)
// * Math.pow -> leverage binary multiplication concept (cool)
class Solution {
    public int strStr(String haystack, String needle) {
        if (null == haystack) return -1;
        if (null == needle) return -1;
        if (needle.isEmpty()) return 0; // if empty string, return 0
        if (haystack.length() < needle.length()) return -1;

        int magicNum = 31; // for hashing
        // int base = 1000000; // if num too big, you need this to %

        // get multiply num for later use (represent the first char of each-round substring)
        int power = 1;
        for (int k = 0 ; k < needle.length() - 1; k++) { // attention: you only need length() - 1 multiplations
            power = power * magicNum;
        }

        // get target case:
        int targetHashNum = 0;
        for (int n = 0; n < needle.length(); n++) {
            targetHashNum = targetHashNum * magicNum + needle.charAt(n); // for loop AND * magicNum ==> Math.pow() //
                                                                 // like what we do for binary * 2, move left
        }

        // get base case
        int nowHashNum = 0;
        for (int i = 0; i < needle.length(); i++) {
            nowHashNum = nowHashNum * magicNum + haystack.charAt(i); // for-loop AND * magicNum ==> Math.pow()
                                                             // however, Math.pow(): Double force us to deal
                                                             // with type conversion
        }

        // main code
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            if (i != 0) { // skip base case
                // abc - a
                nowHashNum = nowHashNum - ( haystack.charAt(i-1) * power);

                // bc + d
                nowHashNum = (nowHashNum * magicNum); // move left
                nowHashNum = nowHashNum + haystack.charAt(i+needle.length()-1); // + d
            }

            // 1st layer check: hashing
            if (nowHashNum == targetHashNum) {
                // 2nd layer check: cuz hash, we still have to make sure, it is actually the same
                if (haystack.substring(i, i+needle.length()).equals(needle)) {
                    return i;
                }
            }

        }

        return -1;
    }

};