Hey I'm having problems with this class I wrote. It's for the Boyer Moore Algorithm, I basically copied my working Horspool's Algorithm class and added the suffix table part, that's the only change. I haven't gotten the BoyerMooreAlgorithm to run yet. So if you notice I have a constructor which gets passed a string called pattern. It's saved in this->pattern which I can access throughout everything in that constructor and any functions the constructor calls for setup. However, when I call the search algorithm, the (this->pattern).length() errors and it appears from testing that this is do to this->pattern being null. For the life of me I can't figure this out because all that I do is the following in main.cpp:
BoyerMooreAlgorithm* boyer = new BoyerMooreAlgorithm( "hello" );
boyer->search("Text to find hello in");
This really isn't a boyer moore question since I will be able to implement it fine once I can do a test run of this code. I just need to figure out what happens to the this->pattern string.
Any help would be so gratefully appreciated and I'm just giving a thanks ahead of time for all of you for even looking at it let alone if you can help me. Thanks.
---- BoyerMooreAlgorithm.h
#pragma once
#include <string>
#include <iostream>
using namespace std;
class BoyerMooreAlgorithm
{
private:
string pattern;
int shiftTable[256];
int suffixTable[256];
void findShiftTable(void);
void findSuffixTable(void);
public:
BoyerMooreAlgorithm(string);
~BoyerMooreAlgorithm(void);
int search(string);
};
---- BoyerMooreAlgorithm.cpp
#include "boyermoorealgorithm.h"
BoyerMooreAlgorithm::BoyerMooreAlgorithm( string pattern )
{
this->pattern = pattern;
this->findShiftTable();
this->findSuffixTable();
}
BoyerMooreAlgorithm::~BoyerMooreAlgorithm(void)
{
}
int BoyerMooreAlgorithm::search( string text )
{
int k;
bool match = true;
int i = ((this->pattern).length())-1;
int patternLength = this->pattern.length();
while( i < text.length() )
{
match = true;
k = 0;
for( ; k < patternLength && match ; k++ )
{
if( !( this->pattern[ patternLength - k - 1 ] == text[ i - k ] ) )
{
match = false;
}
}
if( k == (patternLength - 1) && match )
{ return i - patternLength + 1; }
else
{
i = i + max( max( this->shiftTable[(int)text[i]] , 1 ) , this->suffixTable[k] );;
}
}
return -1;
}
void BoyerMooreAlgorithm::findShiftTable( void )
{
int letter;
int patternLength = (this->pattern).length();
/*** Initialize Shift Table ***/
for( int i = 0 ; i < 257 ; i++ )
{
this->shiftTable[i] = patternLength;
}
/*** Compute Shift Table ***/
for( int i = 0 ; i < patternLength - 1 ; i++ )
{
this->shiftTable[(int)this->pattern[i]] = patternLength - 1 - i;
}
}
void BoyerMooreAlgorithm::findSuffixTable( void )
{
int letter;
int patternLength = (this->pattern).length();
string pattern = this->pattern;
for( int i = 1 ; i < patternLength && i < 255 ; i++ ) {
int temp = pattern.rfind( pattern.substr( patternLength - i , i ) , patternLength - i - 1 );
if( temp == string::npos ) {
suffixTable[i] = patternLength - 1;
} else {
suffixTable[i] = patternLength - temp - i;
}
}
}
edit: Oh and I'm compiling with Visual Studio .NET hence the pragma once
[edited by - Hexxagonal on April 20, 2004 3:17:28 PM]
[edited by - Hexxagonal on April 20, 2004 3:18:16 PM]