rabin-karp.java

public static List<Integer> rabinKarp(String s, String p) {
    int ph = 0;
    for (int i = 0; i < p.length(); i++) {
        char c = p.charAt(i);
        ph = ph*31 + c;
    }

    List<Integer> results = new ArrayList<>();
    int sh = 0;
    for (int i = -p.length()+1; i < s.length()-p.length()+1; i++) {
        if (i-1 >= 0) {
            int pow = (int)Math.pow(31, p.length()-1);
            sh -= s.charAt(i-1)*pow;
        }
        sh *= 31;
        sh += s.charAt(i+p.length()-1);
        if (sh == ph && i >= 0 && isEqual(s, i, p)) {
            results.add(i);
        }
    }
    return results;
}

private static boolean isEqual(String s, int i, String p) {
    for (int j = 0; j < p.length(); j++) {
        if (s.charAt(i+j) != p.charAt(j))
            return false;
    }
    return true;
}