Алгоритм Бойера-Мура использует тот факт, что при поиске, скажем, «HELLO WORLD» в более длинной строке буква, которую вы найдете в данной позиции, ограничивает то, что можно найти вокруг этой позиции, если совпадение вообще должно быть найдено, sort игры Naval Battle: если вы обнаружите открытое море в четырех клетках от границы, вам не нужно проверять четыре оставшиеся клетки на случай, если там прячется 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 плюс один (не, как я писал в предыдущей редакции, плюс длина игольной нити; см. комментарий).
Этот подход также будет сообщать о совпадающих совпадениях, например, поиск ana в банане найдет b * ana * na и запретит * ana < / em> *.
ОБНОВЛЕНИЕ
Я проверил вышесказанное, и, похоже, он работает. Я изменил код Википедии, добавив эти два включения, чтобы 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;
}
person
LSerni
schedule
03.10.2012
