for(j=nlen-1, k=i, i++;
(j>=0) && (needle[j]==haystack[k]);
j--, k--);
Если найдена подстрока j=-1, иначе j>=0.
Условие внешнего цикла:
while((i<hlen)&&(j>=0))
Пример программы:
#include <stdio.h>
#include <math.h>
char stop_table[256];
void stop_table_init(char* needle, int nlen)
/*
Заполняет таблицу стоп-символов
*/
{
int i;
for(i=0; i<256; i++) stop_table[i]=nlen;
for(i=0; i<nlen-1; i++) stop_table[needle[i]]=nlen-i-1;
}
int search_bmh(char* needle, int nlen, char* haystack, int hlen)
/*
Поиск подстроки needle длиной nlen в строке haystack длиной hlen.
Алгоритм Бойера — Мура — Хорспула.
*/
{
int i=nlen-1, j=1, k;
while((i<hlen)&&(j>=0))
{
if (needle[nlen-1]!=haystack[i])
{
i=i+stop_table[haystack[i]];
}
else
for(j=nlen-1, k=i, i++; (j>=0)&&(needle[j]==haystack[k]); j--, k--);
}
if (j<0) return i-nlen+1; else return 0;
}
main()
{
char haystack[] = "acabcabacc";
char needle[3][4] = {"cc",
"aca",
"bca"};
int len[]={2, 3, 3};
int ans[]={9, 1, 4};
int i, ntest=3, n;
for(i=0;i<ntest;i++)
{
printf("test %i\n", i);
stop_table_init(needle[i], len[i]);
n = search_bmh(needle[i], len[i], haystack, sizeof(haystack)-1);
printf("Substring \"%s\" in string \"%s\" in %i position\n", needle[i], haystack, n);
if (n==ans[i]) printf("test passed\n\n");
else printf("test failed\n\n");
}
}
