FastRabinKarpHashFunction.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public final class FastRabinKarpHashFunction {

    private final int[] map;
    private final int[] factors;
    private final int q;

    /**
     * Builds this hash function data structure in time and space linear in the
     * length of the integer string.
     *
     * @param s the string in integer alphabet.
     * @param r the r.
     * @param q the q.
     */
    public FastRabinKarpHashFunction(int[] s, int r, int q) {
        this.q = q;
        int n = s.length + 1;
        this.map = new int[n];
        
        // Compute the Karp-Rabin hash functions for all the prefixes of
        // the string.
        int hash = 0;
        
        for (int i = 1; i < map.length; ++i) {
            hash *= r;
            hash += s[i - 1];
            map[i] = hash;
        }

        this.factors = new int[n];

        for (int i = 0, factor = 1; i < n; ++i, factor *= r) {
            factors[i] = factor;
        }
    }

    public long getHashValue(int i, int j) {
        if (i < 0) {
            throw new IndexOutOfBoundsException(
                    "The starting index is negative: " + i);
        }

        if (j >= this.map.length) {
            throw new IndexOutOfBoundsException(
                    "The ending index is too large: " + j + ", should be "
                    + "at most " + this.map.length + ".");
        }

        if (i > j) {
            throw new IllegalArgumentException(
                    "The indices are ass-backwards: i = " + i + ", j = "
                    + j);
        }

        int len = j - i;
        long factor = factors[len];
        long a = map[j];
        long b = map[i];
        long ret = (a - b * factor) % q;
        return ret < 0 ? ret + q : ret;
    }
    
    public static void main(String[] args) {
        int r = 37;
        int q = 11;
        int[] str = new int[]{ 2, 1, 1, 4, 3 };
        
        if (args.length > 2) {
            r = Integer.parseInt(args[0]);
            q = Integer.parseInt(args[1]);
            List<Integer> integerString = new ArrayList<>(args.length - 2);
            
            for (int i = 2; i < args.length; ++i) {
                integerString.add(Integer.parseInt(args[i]));
            }
            
            str = new int[integerString.size()];
            
            for (int i = 0; i < str.length; ++i) {
                str[i] = integerString.get(i);
            }
        }
        
        FastRabinKarpHashFunction f = new FastRabinKarpHashFunction(str, r, q);
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            int index1 = scanner.nextInt();
            int index2 = scanner.nextInt();
            System.out.println("H(" + getSubstring(str, index1, index2) + 
                                ") = " + f.getHashValue(index1, index2));
        }
    }
    
    private static String getSubstring(int[] arr, int i, int j) {
        StringBuilder sb = new StringBuilder();
        
        for (int k = i; k < j; ++k) {
            sb.append(arr[k]);
            
            if (k < j - 1) {
                sb.append(", ");
            }
        }
        
        return sb.toString();
    }
}