@Override
	public List<Integer> rabinKarp(String needle, String haystack) {
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		int base = BASE;
		int power = pow(base, needle.length() - 1);
		int hash = generateHash(needle);
		int prev = generateHash(needle);
		if (prev == hash && check(needle, haystack, 0)) {
			return null;
		}
		for (int i = 1; i < haystack.length() - needle.length() + 1; i++) {
			prev = updateHash(prev, needle.length(), haystack.charAt(i - 1), haystack.charAt(i + needle.length() - 1));
			if (prev == hash && check(needle, haystack, i)) {
				toReturn.add(i);
				return toReturn;
			}
		}
		toReturn.add(-1);
		return toReturn;
	}

	private boolean check(String needle, String haystack, int start) {
		if (start + needle.length() - 1 >= haystack.length()) {
			return false;
		}
		for (int i = 0; i < needle.length(); i++) {
			if (needle.charAt(i) != haystack.charAt(i + start)) {
				return false;
			}
		}
		return true;
	}