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% [?]
