Horspool Algorithm for String Matching

[mcook228]

I'm working on this program that implements the Horspool string matching algorithm. The program reads in a text file and searches for the pattern text provided in main.cpp. The StringMatcher class is supposed to return the index of the first letter of the pattern in the text and count the number of comparisons per character passed (CPCP). For some reason, it's not comparing the first letter in the word and it's returning garbage for the index.

I've been looking at this for about 3 hours now and I'm not seeing it... I would really appreciate another set of eyes (or several) to help me figure out where my loop is going wrong...

Thank you!

main.cpp

#include "StringMatcher.h"
#include <fstream>
#include <string>
#include <iomanip>
#include <iostream>
#include <istream>
#include <cstdlib>
#include <vector>

using namespace std;

int main(int argc, char ** argv) {

     int comparisons=0;
     StringMatcher matcher("Text.txt");

     // Find the first match, if any:

     size_t position = matcher.FindMatch("Discipline", comparisons);
     cout << position << endl;

     while ( position != string::npos ) {
     // process the search result...
     // Now find the next match, if any:
          position = matcher.FindMatch("Discipline",position + 1,comparisons);
          cout << position << endl;
     }
     return 0;
}

StringMatcher.cpp

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>

#include "StringMatcher.h"

using namespace std;

StringMatcher::StringMatcher(){
}

StringMatcher::StringMatcher(string filename){
     ifstream inFileText(filename.c_str());
     if (inFileText.fail()) {
          cout <<"Could not open text file.." << endl;
     }

// create vector to store Text data and read in data
     char text;
     while (inFileText.good()) {
          inFileText.get(text);
          text = tolower(text);

          if(text !='\n' || '\t') {
               vText.push_back(text);
          }
          else {
               vText.push_back(' ');
          }
     }
}

    
StringMatcher::~StringMatcher(){
}

size_t StringMatcher::FindMatch(std::string pattern,int &comparisons){
     return FindMatch(pattern, 0, comparisons);
}

size_t StringMatcher::FindMatch(std::string pattern,size_t startPosition,int &comparisons){
     int shiftTable[256];
     int patternLength = pattern.size();
     int i;

     for(i=0; i<256; i++){
          shiftTable[i]=patternLength;
     }

     for(i=0; i<patternLength-1; i++){
          shiftTable[pattern[i]]=patternLength-1-i;
     }

     int m = patternLength;
     int n = vText.size();
     i = m-1;

     while(i < n-1){
          int k = 0;

          while((k <= m-1) && (pattern[m-1-k] == vText[i-k])){
               cout << "comparing pattern " << pattern[m-1-k] << " with text " << vText[i-k] << endl;
               k++;
               comparisons++;
               cout << "comparisons is " << comparisons << endl;
          }
          if(k==m){
               return i-m+1;
          }
          else {
               cout << "i = " << i << " + " << shiftTable[vText[i]] << " = ";

               i=i+shiftTable[vText[i]];
               cout << i << endl;
          }
     } return -1;
}

Just out of interest wat's stringmatcher.h

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[mcook228]

This is my StringMatcher.h file

#include <iostream>
#include <vector>
using namespace std;

class StringMatcher {
     public:
          StringMatcher();
          StringMatcher(std::string filename);
          ~StringMatcher();
          size_t FindMatch(std::string pattern,int &comparisons);
          size_t FindMatch(std::string pattern,size_t startPosition,int &comparisons);

     private:
          vector<char> vText;    
};

Is this any good?

http://www.glenmccl.com/bmh.htm

And lest we forget.
http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]

[mcook228]

I'm still not having any luck with this... I used the algorithm out of our class text. I also looked at the references you provided and tried to implement those algorithms and they're not working. The comparisons are fine, but I'm not ever hitting the loop to tell me that a match was found and at what index.

Well, if that's the case, you need to systematically test each method, bit by bit.

This way you are more likely to find the error. It could be something simple, it could be something more involved.

[IMG]http://img476.imageshack.us/img476/5171/cut20ln.png[/IMG]
Piworld ™
[Tis simple as Pie]