Tech Guide Blog

This time, we will talk about Boyer Moore string searching. It’s not like brute-force, it will search a substring from the back and go forward till the first char of string. For example, we search a substring EXAMPLE within HERE IS A SIMPLE EXAMPLE string. I can’t explain it well, so this below maybe rather confusing.

EXAMPLE
HERE IS A SIMPLE EXAMPLE
's' is not in EXAMPLE substring, jump for EXAMPLE length = 7
       EXAMPLE
HERE IS A SIMPLE EXAMPLE
'e' is not same as 'p', so jump for the last char of EXAMPLE to 'p' EXAMPLE = 2
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
'a' != 'i', jump for distance from 'e' SIMPLE to the front 'e' EXAMPLE sub string = 6
               EXAMPLE
HERE IS A SIMPLE EXAMPLE
'e' is not same as 'p', so jump for the last char of EXAMPLE to 'p' EXAMPLE = 2
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
compare till end, found.

For the code, it’s a little weird, made by myself with many helps. It just find the index of string if it found the sub string within the string. You can use a table to save all chars shift value.

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <windows.h>

void main()
{
	char string[1000], substring[1000];
	int strvalue[256], i, j, diff = 0, count = 0;

	printf("Input string: ");
	gets(string);
	printf("Input substring: ");
	gets(substring);
	for (i = 0; i < 256; i++)
	{
		strvalue[i] = -1;
	}
	for (i = strlen(substring) - 1; i >= 0 ; i--)
	{
		if (strvalue[substring[i]] == -1)
			strvalue[substring[i]] = i;
	}
	for (i = 0; i < 256; i++)
	{
		if (strvalue[substring[i]] == -1)
			strvalue[substring[i]] = strlen(substring);
	}
	i = strlen(substring) - 1;
	while (true)
	{
		for (j = strlen(substring) - 1; j >= 0 ; j--)
		{
			if (substring[j] == string[i - diff])
			{
				count++;
				diff++;
			}
			else
				break;
			if (count == strlen(substring))
			{
				printf("%d", i - diff + 2);
				getch();
				exit(0);
			}
		}
		diff = strlen(substring) - strvalue[string[i - diff]] - 1 - count;
		if (diff > 0)
		{
			i = i + diff;
			diff = 0;
			count = 0;
		}
		else
			i++;
		if (i > strlen(string) + strlen(substring) + 2)
			exit(0);
	}
}

Popularity: 67% [?]