title: Implementation of Boyer Moore Horsepool algorithm with wildcards
body: <p>I want to implement a generalization of the Boyer Moore Horspool algorithm that takes care of wildcards (match any letter in the word). This means that the pattern <code>h _ _ s e</code> would be found two times in this text: <code>horsehouse</code>.</p>
  
  <p>I need help to implement this, I cant get deep enough understanding of the algorithm to figure this out by myself, some tips ?</p>
  
  <pre><code>int [] createBadCharacterTable(char [] needle) {
  
          int [] badShift = new int [256];
  
          for(int i = 0; i &lt; 256; i++) {
              badShift[i] = needle.length;
          }
  
          int last = needle.length - 1;
  
          for(int i = 0; i &lt; last; i++) {
              badShift[(int) needle[i]] = last - i;
          }
  
          return badShift;
      }
  
      int boyerMooreHorsepool(String word, String text) {
  
          char [] needle = word.toCharArray();
          char [] haystack = text.toCharArray();
  
          if(needle.length &gt; haystack.length) {
              return -1;
          }
  
          int [] badShift = createBadCharacterTable(needle);
  
          int offset = 0;
          int scan = 0;
          int last = needle.length - 1;   
          int maxoffset = haystack.length - needle.length;
  
          while(offset &lt;= maxoffset) {
              for(scan = last; (needle[scan] == haystack[scan+offset] ||  needle[scan] == (int) '_'); scan--) {
  
                  if(scan == 0) { //Match found
                      return offset;
                  }
              }
              offset += badShift[(int) haystack[offset + last]];
          }
          return -1;
      }
  </code></pre>