javaalgorithmsubstringrabin-karp

Rabin Karp algorithm runs slower than naive

I implemented the Rabin-Karp algorithm but it runs slower than the naive string search (this is not for an assignment, I'm just coding it to understand it better).

Rabin Karp (I'm using 128 as the base for ascii):

    public long honer(String s){
        long value = (int)s.charAt(0);
        for(int i = 0; i < s.length() - 1; i++){
            value = value*baseASCII + (int)s.charAt(i + 1);
        }
        return value;
    }
    public long updateHoner(Character c0, long honerNumber, Character c4, int length){
        long newNumber = (honerNumber - (int)c0*(long)Math.pow(baseASCII, length))*baseASCII + (int)c4;

        return newNumber;
    }
    public void rabinKarp(String subString){
        long subStringValue = honer(subString);
        long sValue = honer(string.substring(0, subString.length()));
        if(subStringValue == sValue){
            //p.println("match found at index 0");
        }

        for(int i = 1; i <= string.length() - subString.length(); i++){
            sValue = updateHoner(string.charAt(i-1), sValue, string.charAt(i+subString.length()-1), subString.length() - 1);

            if(sValue == subStringValue){
                //p.println("match found at index " + i);
            }
        }
    }

Naive algorithm:

public void naiveFinder(String subString){
        String found = "";
        for(int i = 0; i <= string.length() - subString.length(); i++){
            for(int j = 0; j < subString.length(); j++ ){
                if(string.charAt(i+j) == subString.charAt(j)){
                    found += string.charAt(i+j);
                }
                else{
                    // reset the string and continue with the next char
                    found = "";
                    break;
                }
                if(found.length() == subString.length()){
                    found = "";
                    //p.println(subString + " found at index " + (i));
                }
            }
        }
    }

Test (main):

static void main(){
        long init, after;
        StringFinder sf = new StringFinder(getString());
        init =  Calendar.getInstance().getTimeInMillis();
        for(int i = 0; i < 10000; i++)
            sf.rabinKarp("roll");
        after =  Calendar.getInstance().getTimeInMillis();
        p.println("rabin karp without mod : " + (after - init));

        init =  Calendar.getInstance().getTimeInMillis();
        for(int i = 0; i < 10000; i++)
            sf.naiveFinder("roll");
        after =  Calendar.getInstance().getTimeInMillis();
        p.println("naive : " + (after - init));
    }

The result is that it took 2517 ms to run the Rabin-Karp algorithm, but only 675 ms to run the naive algorithm. I'm suspecting that it's updateHoner() that's taking a really long time but I'm not sure. Any insight would be really appreciated.

Thanks

Edit: misspelling

Solution

  • In updateHoner():