String Matching-Horspool\'s Algorithm Would someone mind creating a code that ut
ID: 3695090 • Letter: S
Question
String Matching-Horspool's Algorithm
Would someone mind creating a code that utilizes Horspool's Algorithm of String-Matching. Pseudocode is as follows:
//Input: Pattern (P[0..m-1], and Text T[0..n-1])
//Output: The index of the left end of the first matching substring
or -1 if no matches ShiftTable(P[0..m-1]) //generate table of shifts
i <----(arrow) m-1 //position of the pattern's right end
while i (less than/ equal to) n-1....do
k<----0// number of matched characters
while k (less than/equal to m -1 and P[m-1-k]= T[i-k] do
k <-----k+1
if k = m return i -m+1
else i<----- i+Table[T][i]
return -1
Explanation / Answer
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// bfStrMatch
// String matching - brute-force algorithm
// Given range of characters in [first, last), and pattern to match in
// pattern, returns vector holding index of start of first match, if
// any; vector is empty if no match.
// Requirements on Types:
// RAIter must be a random-access iterator type.
// The value type of RAIter must be char.
// Pre:
// [first, last) is a valid range.
// Post:
// Return value is empty iff no match.
// If return value is nonempty, then its size is 1, and it's sole
// item is the index in the [first, last) of the start of the first
// match.
template <typename RAIter>
vector<size_t> bfStrMatch(RAIter first, RAIter last,
const string & pattern)
{
vector<size_t> result; // Vector to hold return value
size_t size = last-first; // Size of text ("n"0
size_t len = pattern.size(); // Length of pattern ("m")
// Handle trivial case: zero-length pattern always matches
if (len == 0)
{
result.push_back(0);
return result;
}
// Do the search from the beginning of the text
for (size_t loc = 0; loc+len <= size; ++loc)
// loc is current search location in text
{
// Check match against pattern right-to-left
size_t k = len;
while (true)
{
--k;
if (first[loc+k] != pattern[k])
break;
if (k == 0)
{ // Found! Return location
result.push_back(loc);
return result;
}
}
}
// Return not-found result
return result;
}
// hStrMatch
// String matching - Horspool's Algorithm
// [Remainder of documentation identical to function bfStrMatch]
template <typename RAIter>
vector<size_t> hStrMatch(RAIter first, RAIter last,
const string & pattern)
{
vector<size_t> result; // Vector to hold return value
size_t size = last-first; // Size of text ("n"0
size_t len = pattern.size(); // Length of pattern ("m")
// Handle trivial case: zero-length pattern always matches
if (len == 0)
{
result.push_back(0);
return result;
}
// Make bad-symbol shift table
vector<size_t> badsymbol(256, len); // 256 possible char values
for (size_t i = 0; i != len-1; ++i)
{
badsymbol[pattern[i]] = len - 1 - i;
}
// Do the search from the beginning of the text
size_t loc = 0; // loc is current search location in text
while (loc+len <= size)
{
// Check match against pattern right-to-left
size_t k = len;
while (true)
{
--k;
if (first[loc+k] != pattern[k])
break;
if (k == 0)
{ // Found! Return location
result.push_back(loc);
return result;
}
}
// Did not find yet; advance loc using bad-symbol shift table
char c = first[loc+len-1];
loc += badsymbol[c];
}
// Return not-found result
return result;
}
// testMatch
// Test String matching functions bfStrMatch, hStrMatch on given text,
// pattern. Print pattern & then output for each function, followed by
// a blank line.
void testMatch(const string & text, const string & pattern)
{
// Print pattern
cout << "Pattern: [" << pattern << "]" << endl;
// Print brute-force matching results
vector<size_t> bfresult =
bfStrMatch(text.begin(), text.end(), pattern);
cout << "Brute Force: ";
if (bfresult.empty())
cout << "NO match" << endl;
else
cout << "MATCH - " << bfresult[0] << endl;
// Print Horspool's Algorithm results
vector<size_t> hresult =
hStrMatch(text.begin(), text.end(), pattern);
cout << "Horspool's: ";
if (hresult.empty())
cout << "NO match" << endl;
else
cout << "MATCH - " << hresult[0] << endl;
// End with a blank line
cout << endl;
}
// Main program
// Test string matching functions using function testMatch
int main()
{
// Text to search in
string text = "acbaababcbabac";
cout << "Text: [" << text << "]" << endl;
cout << endl;
// Test 1
testMatch(text, "abc");
// Test 2
testMatch(text, "abx");
// Test 3
testMatch(text, "");
cout << "Press ENTER to quit ";
while (cin.get() != ' ') ;
return 0;
}
/*
Sample run:
Text: [acbaababcbabac]
Pattern: [abc]
Brute Force: MATCH - 6
Horspool's: MATCH - 6
Pattern: [abx]
Brute Force: NO match
Horspool's: NO match
Pattern: []
Brute Force: MATCH - 0
Horspool's: MATCH - 0
Press ENTER to quit
*/