CareerCup_1.8 - StringRotationDetector

StringRotationDetector.java

package Chapter1;

public class StringRotationDetector {

    private static int[] initOccurance(String s) {
	int[] rightMostOccurance = new int[256];
	for (int i = 0; i < 256; i++)
	    rightMostOccurance[i] = -1;
	for (int i = 0; i < s.length(); i++)
	    rightMostOccurance[s.charAt(i)] = i;
	return rightMostOccurance;
    }

    // check if target is a sub string of origin
    // Boyer-Moore algorithm
    private static boolean isSubString(String str, String subStr) {
	if (str == null || (subStr == null || subStr.length() > str.length()))
	    return false;
	if (subStr == "")
	    return true;

	int[] rightMostOcc = initOccurance(subStr);
	int n = str.length();
	int m = subStr.length();
	int jump = 0;// how far the search jump

	for (int i = 0; i <= n - m; i += jump) {
	    jump = 0;
	    for (int j = m - 1; j >= 0; j--) {
		if (str.charAt(i + j) != subStr.charAt(j)) {
		    jump = Math.max(j - rightMostOcc[str.charAt(i + j)], 1);
		    break;
		}
	    }
	    if (jump == 0) return true;
	}
	return false;
    }

    // check whether target is a rotation of origin string
    public static boolean isRotation(String origin, String target) {
    	if(origin.length() != target.length()) return false;
	return isSubString(origin + origin, target);
    }

    public static void main(String[] args) {
	System.out.println("isRotation(empty, empty) = " + isRotation("", ""));
	System.out.println("isRotation(erbottlewat, waterbottle) = " + isRotation("erbottlewat", "waterbottle"));
    }
}