686. Repeated String Match

Problem Statement

Pattern:

---

Solution

public static int getIndex(String pattern, String text) {
	int n = pattern.length(), m = text.length(),
		base = 128, prime = 8_388,
		nbase = 1, pHash = 0, tHash = 0;
	if(m < n) return -1;
 
	// get nbase
	for(int i = 0; i < n-1 ; i++) nbase = (nbase * base) % prime;
 
	// get pattern & text hash
	for (int i = n - 1; i >= 0; i--) {
		pHash = (base * pHash + pattern.charAt(n-1-i)) % prime;
		tHash = (base * tHash + text.charAt(n-1-i)) % prime;
	}
 
	// roll hash
	if(tHash == pHash && text.substring(0, n).equals(pattern)) return 0;
	for (int i = 1; i <= m-n; i++) {
		// update text hash
		int pre = text.charAt(i-1), post = text.charAt(i+n-1);
		tHash = (base * (tHash - (pre * nbase)) + post) % prime ;
		if(tHash < 0) tHash += prime; // Avoid Integer Overflow
		// compare hashes
		if(tHash == pHash && text.substring(i, i+n).equals(pattern)) return i;
	}
	return -1;
}
 
public int repeatedStringMatch(String a, String b) {
	int times = (b.length() + a.length() - 1) / a.length();
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < times; i++) sb.append(a);
 
 
	if(getIndex(b, sb.toString()) != -1) return times;
	if(getIndex(b, sb.append(a).toString()) != -1) return times +1;
	return -1;
}

TC : $\theta (max(m,n))$ SC : $\theta (m)$

Notes

• quite simple