[Leetcode] Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

I use this problem to check the implementation of Rabin-Karp algorithm in the last post. A thing need to pay attention is overflow, we could use a smaller prime or we use long to store the hash number.

    public String strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if(n < m)
            return null;
        int h1 = 0, h2 = 0, h = 1;
        int d = 256, q = 9973;
        
        for(int i = 0; i < m-1; i++)
            h = (h * d) % q;
        for(int i = 0; i < m; i++) {
            h1 = (h1 * d + haystack.charAt(i)) % q;
            h2 = (h2 * d + needle.charAt(i)) % q;
        }
        
        for(int i = 0; i <= n-m; i++) {
            if(h1 == h2) {
                boolean flag = true;
                for(int j = 0; j < m; j++) {
                    if(haystack.charAt(i+j) != needle.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if(flag == true)
                    return haystack.substring(i);
            }
            else {
                if(i < n-m) {
                    h1 = ((h1 - haystack.charAt(i) * h) * d + haystack.charAt(i+m)) % q;
                }
                if(h1 < 0)
                    h1 = h1 + q;
            }
        }
        
        return null;
    }