Horsepool.cpp

#include <iostream>
using namespace std;
# define NO_OF_CHARS 256


void badCharHeuristic( string str, int size,
                       int badchar[NO_OF_CHARS])
{
    int i;


    for (i = 0; i < NO_OF_CHARS; i++)
        badchar[i] = -1;


    for (i = 0; i < size; i++)
        badchar[(int) str[i]] = i;
}


void searchh( string txt, string pat)
{
    int m = pat.size();
    int n = txt.size();

    int badchar[NO_OF_CHARS];


    badCharHeuristic(pat, m, badchar);

    int s = 0;

    while(s <= (n - m))
    {
        int j = m - 1;


        while(j >= 0 && pat[j] == txt[s + j])
            j--;


        if (j < 0)
        {
            cout << "pattern occurs at shift = " << s << endl;


            s += (s + m < n)? m-badchar[txt[s + m]] : 1;

        }

        else

            s += max(1, j - badchar[txt[s + j]]);
    }
}




int main()
{
    string s;
    cout<<"Enter Message:";
    getline(cin,s);
    string pat;
    cout<<"Enter Pattern :";
    cin>>pat;
    searchh(s,pat);
}