686. Repeated String Match

;  |     Back to Homepage   |     Back to Code List


class Solution {
    public int repeatedStringMatch(String A, String B) {
        int base = 31, mod = 100000007;
        int len1 = A.length(), len2 = B.length();
        int maxLen = len2 + len1;

        long[] hashA = new long[maxLen];
        hashA[0] = A.charAt(0);
        long hashB = B.charAt(0);
        long basePower = base;

        for (int i = 1; i < len2; i++) {
            hashA[i] = (hashA[i - 1] * base) % mod + A.charAt(i % len1) ;
            hashB = (hashB * base + B.charAt(i)) % mod;
            basePower = (basePower * base) % mod;
        }

        if (hashA[len2 - 1] == hashB) {
            return len2 % len1 == 0 ? len2 / len1 : len2 / len1 + 1;
        }

        for (int i = len2; i < maxLen; i++) {
            hashA[i] = (hashA[i - 1] * base) % mod + A.charAt(i % len1);
            hashA[i] = hashA[i] + mod - (A.charAt((i - len2) % len1) * basePower) % mod;

            if (hashA[i] % mod == hashB) {
                return (i + 1) % len1 == 0 ? (i + 1) / len1 : (i + 1) / len1 + 1;
            }
        }

        return -1;
    }
}