rabin

/* Boyer moore string search algorithm */

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

using namespace std;

#define char_limit 256

void stringCheck(string str, int size,
	int check[char_limit])
{
	int i;

	for (i = 0; i < char_limit; i++)
		check[i] = -1;

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

int max(int a, int b)
{
	return (a > b) ? a : b;
}

void stringCheck(char* str, int size, int check[char_limit])
{
	int i;

	for (i = 0; i < char_limit; i++)
		check[i] = -1;

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

void searchString(char* text, char* seq)
{
	int x = strlen(seq);
	int y = strlen(text);

	int check[char_limit];

	stringCheck(seq, x, check);

	int s = 0;

	printf("\tBOYER MOORE ALGORITHM\n");

	while (s <= (y - x))
	{
		int j = x - 1;

		while (j >= 0 && seq[j] == text[s + j])
			j--;

		if (j < 0)
		{
			printf("\n A sequence has matched after character = %d", s);

			s += (s + x < y) ? x - check[text[s + x]] : 1;

		}

		else
			s += max(1, j - check[text[s + j]]);
	}
}

/* main program searching for sequence in given text*/
int input()
{
	char text[] = "B C A D F B A A D D C B C A B A F C C B A B C A B B B A F A D D C D A C B A D F A A B C C C D D D F F B A B C D D C C C D D C C D D F A F A D D C D A C B A D F A A B C C C D D D F F B A B C D D C C C D D F F A D A F A D D C D A C B A D F A A B C C C D D D F F B A B C D D C C C D D C D B A C D D B C A";
	char seq[] = "A";
	searchString(text, seq);
	return 0;
}