# Boyer Moore Horspools String Searching - JAVA



## r3drock3t88 (Jan 13, 2007)

Hey all,

I am just fooling around with some searching algorithms for extra practice but came up to a problem I cannot seem to figure out. I am trying to get the boyer-moore horspool algorithm to work properly, but for some reason it will not tell when a match arrives.

Here is the code...


```
import java.util.ArrayList;
import java.util.HashMap;

public class horsepools {

	void horse(String text, int textLength, String key, int keyLength)
	{
		boolean match = false;
		char [] keyArray, textArray;
		
	    int scan = 0;
	    int bad_char_skip[]; /* Officially called:*/
	    int origLen = textLength;

	    keyArray = key.toCharArray();
	    textArray = text.toCharArray();
	    
	    bad_char_skip = new int[256];
	    //PREPROCESSING
	    //This loop initializes the search table to the length
	    //of the pattern being searched
	    for (scan = 0; scan <= 255; scan = scan + 1)
	    {
	        bad_char_skip[scan] = keyLength;
	       // System.out.println("badchar: " + bad_char_skip[scan]);
	    }
	    /* C arrays have the first byte at [0], therefore:
	     * [nlen - 1] is the last byte of the array. */
	    int last = keyLength - 1;

	    /* Then populate it with the analysis of the needle */
	    for (scan = 0; scan < keyLength; ++scan)
	    {
	        bad_char_skip[keyArray[scan]] = last - scan;
	        System.out.println("last: " + last);
	        System.out.println("badchar: " +  bad_char_skip[keyArray[scan]]);
	    }


	    
	    /* ---- Do the matching ---- */

	    /* Search the haystack, while the needle can still be within it. */
	    while (textLength >= keyLength)
	    {
	    //	System.out.println("scan2: " + scan);
	        /* scan from the end of the needle */
	        for (scan = last; textArray[scan] == keyArray[scan]; scan = scan - 1)
	        {
	            if (scan == 0) /* If the first byte matches, we've found it. */
	            {
	                System.out.println("match found");
	               

	            }
	        }
	        
	        textLength    -= bad_char_skip[textArray[last]];
	        text += bad_char_skip[textArray[last]];
	    	
	    	
	    }
	    	
	}

	       
	    

	

	
}
```
Thank you all in advance for your help at helping me understand why the matching won't work right.


----------



## lotuseclat79 (Sep 12, 2003)

Hi r3drock3t88,

The Boyer-Moore-Horspool algorithm is one of my favorite - I think I had read about it in the journal Software Practice & Experience (with a pseudo-code example). I once implemented it in C (based on that psuedo-code example) to be able to scan a file system OS release for license compatibility and it worked very well - the size of the key to scan for was the entire size of the license, which was about 1024 characters or in that range. It ran very fast! 

I would recommend running your code via a Java debugger to find the problem - if there is such a thing. When coding in C, etc. I always ran my code through a gdb debugger (Gnu C or gcc debugger) during code development - quick turnaround can always be had by integrating the use of the language based debugger for the language you are developing your program into your code development process.

Use watchpoints in the code where the comparison is made which should tell you why the problem is occurring straight away.

-- Tom


----------

