Адаптация Бойера-Мура

Алгоритм Бойера-Мура использует тот факт, что при поиске, скажем, «HELLO WORLD» в более длинной строке, буква, которую вы находите в данной позиции, ограничивает то, что можно найти вокруг этой позиции, если совпадение вообще может быть найдено, сортировка в игре «Морской бой»: если вы обнаружите открытое море в четырех клетках от границы, вам не нужно тестировать четыре оставшиеся клетки, если там скрывается 5-клеточный носитель; не может быть

Если вы нашли, например, букву «D» в одиннадцатой позиции, это может быть последняя буква HELLO WORLD; но если вы нашли ‘Q’, ‘Q’ нигде в HELLO WORLD, это означает, что искомая строка не может быть где-либо в первых одиннадцати символах, и вы можете вообще избежать ее поиска. Буква «L», с другой стороны, может означать, что HELLO WORLD находится там, начиная с позиции 11-3 (третья буква HELLO WORLD — L), 11-4 или 11-10.

При поиске вы отслеживаете эти возможности, используя два дельта-массива.

Поэтому, когда вы найдете шаблон, вы должны сделать,

if (j < 0)
{
// Found a pattern from position i+1 to i+1+patlen
// Add vector or whatever is needed; check we don't overflow it.
if (index_size+1 >= index_counter)
{
index[index_counter] = 0;
return index_size;
}
index[index_counter++] = i+1;

// Reinitialize j to restart search
j = patlen-1;

// Reinitialize i to start at i+1+patlen
i += patlen +1; // (not completely sure of that +1)

// Do not free delta2
// free(delta2);

// Continue loop without altering i again
continue;
}
i += max(delta1[string[i]], delta2[j]);
}
free(delta2);
index[index_counter] = 0;
return index_counter;

Это должно вернуть список индексов с нулевым символом в конце, если вы передаете что-то вроде size_t *indexes к функции.

Затем функция вернет 0 (не найдено), index_size (слишком много совпадений) или количество совпадений между 1 и index_size-1.

Это позволяет, например, добавлять дополнительные совпадения без необходимости повторять весь поиск уже найденных (index_size-1) подстрок; вы увеличиваете num_indexes по new_num, realloc indexes массив, а затем передать в функцию новый массив по смещению old_index_size-1, new_num как новый размер и строка стога сена, начиная со смещения соответствия по индексу old_index_size-1 плюс один (не, как я писал в предыдущей редакции, плюс длина игольной струны; см. комментарий).

Этот подход будет сообщать также совпадения совпадений, например, поиск изречений в банан найдет б *изречений* на и бан *изречений*.

ОБНОВИТЬ

Я проверил выше, и это, кажется, работает. Я изменил код Википедии, добавив эти два включения, чтобы gcc не ворчал

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

Затем я изменил if (j < 0) просто вывести то, что он нашел

    if (j < 0) {
printf("Found %s at offset %d: %s\n", pat, i+1, string+i+1);
//free(delta2);
// return (string + i+1);
i += patlen + 1;
j = patlen - 1;
continue;
}

и наконец я проверил с этим

int main(void)
{
char *s = "This is a string in which I am going to look for a string I will string along";
char *p = "string";
boyer_moore(s, strlen(s), p, strlen(p));
return 0;
}

и получил, как и ожидалось:

Found string at offset 10: string in which I am going to look for a string I will string along
Found string at offset 51: string I will string along
Found string at offset 65: string along

Если строка содержит две перекрывающиеся последовательности, ОБА найдены:

char *s = "This is an andean andeandean andean trouble";
char *p = "andean";

Found andean at offset 11: andean andeandean andean trouble
Found andean at offset 18: andeandean andean trouble
Found andean at offset 22: andean andean trouble
Found andean at offset 29: andean trouble

Чтобы избежать совпадений совпадений, самый быстрый способ — не хранить совпадения. Это можно сделать в функции, но это будет означать повторную инициализацию первого дельта-вектора и обновление указателя строки; нам также нужно будет хранить вторую i индекс как i2 чтобы сохранить сохраненные индексы от немонотонности. Это того не стоит. Лучше:

    if (j < 0) {
// We have found a patlen match at i+1
// Is it an overlap?
if (index && (indexes[index] + patlen < i+1))
{
// Yes, it is. So we don't store it.// We could store the last of several overlaps
// It's not exactly trivial, though:
// searching 'anana' in 'Bananananana'
// finds FOUR matches, and the fourth is NOT overlapped
// with the first. So in case of overlap, if we want to keep
// the LAST of the bunch, we must save info somewhere else,
// say last_conflicting_overlap, and check twice.
// Then again, the third match (which is the last to overlap
// with the first) would overlap with the fourth.

// So the "return as many non overlapping matches as possible"// is actually accomplished by doing NOTHING in this branch of the IF.
}
else
{
// Not an overlap, so store it.
indexes[++index] = i+1;
if (index == max_indexes) // Too many matches already found?
break; // Stop searching and return found so far
}
// Adapt i and j to keep searching
i += patlen + 1;
j = patlen - 1;
continue;
}