#include<iostream.h>
#include<string.h>
#include<stdio.h>

#define MAX 100

class horspool
{
	private : char text[MAX];
		  struct code_table
		  {
			char chars;
			int code;
		  } table[MAX];
	public  : void readtext();
		  int matchstring(char [MAX]);
		  int shiftTable(char [MAX]);
		  int getshift(char, int, int);
};

void horspool :: readtext()
{
	cout << "\nEnter the Text : ";
	gets (text);
}

int horspool :: shiftTable(char pattern[MAX])
{
	int i, j, k, plength;
	k = 0;
	plength = strlen(pattern);
	table[k].chars = pattern[0];
	table[k++].code = plength - 1;
	for (i = 1; i < plength - 1; i++)
	{
		for (j = 0; j < i; j++)
		{
			if (pattern[i] == table[j].chars)
				table[j].code = plength - 1 - i;
			else
			{
				table[k].chars = pattern[i];
				table[k++].code = plength - 1 - i;
			}
		}
	}
	return (k - 1);
}

int horspool :: getshift(char t, int codecount, int plength)
{
	int i;
	for (i = 0; i <= codecount; i++)
		if (table[i].chars == t)
			return (table[i].code);
	return plength;
}

int horspool :: matchstring(char pattern[MAX])
{
	int i, k, tlength, plength;
	tlength = strlen(text);
	plength = strlen(pattern);
	int codecount = shiftTable(pattern);
	i = plength - 1;
	while (i <= (tlength - 1))
	{
		k = 0;
		while (k <= plength - 1)
			if (pattern[plength - 1 - k] == text[i - k])
				k = k++;
			else
				break;
		if (k == plength)
			return (i - plength + 1);
		else
			i = i + getshift(text[i], codecount, plength);
	}
	return (-1);
}

int main()
{
	int position;
	char pattern[MAX];
	horspool hs;
	hs.readtext();
	cout << "\nEnter the Pattern : ";
	gets (pattern);
	position = hs.matchstring(pattern);
	if (position < 0)
		cout << "\nThe search Pattern \"" << pattern << "\" does not exist in the Text";
	else
		cout << "\nThe search Pattern \"" << pattern << "\" is found in the Text starting from position : " << position + 1;
	return 0;
}