796. Rotate String

Problem Statement

Rotate String - LeetCode

Pattern:

---

Interview question: Check if one string is a rotation of other string - Stack Overflow

Solution

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

TC : $n\ast m$ SC : $O(n)$

Rabin Karp

Solution

// RABIN KARP ROLLING HASH ALGO
public static int getIndex(String pattern, String text) {
	int n = pattern.length(), m = text.length(),
		set = 128, MOD = 8_388,
		nset = 1, pHash = 0, tHash = 0;
	if(m < n) return -1;
	
	// get nset
	for(int i = 0; i < n-1 ; i++) nset = (nset * set) % MOD;
	
	// get pattern & text hash
	for (int i = n - 1; i >= 0; i--) {
		pHash = (set * pHash + pattern.charAt(n-1-i)) % MOD;
		tHash = (set * tHash + text.charAt(n-1-i)) % MOD;
	}
 
	// 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 = (set * (tHash - (pre * nset)) + post) % MOD ;
		if(tHash < 0) tHash += MOD; // Avoid Integer Overflow
		// compare hashes
		if(tHash == pHash && text.substring(i, i+n).equals(pattern)) return i;
	}
	return -1;
}

TC : $O(m\ast n)$ SC : $O(1)$

Read More