Comments 12
Хорошо бы ещё сравнить с другими альтернативными алгоритмами. А то не понятно чем хорош именно этот алгоритм и чем не устраивает его описание в Википедии (весьма подробное)
Очень не хватает в начале статьи описания соли алгоритма. В чем его основное преимущество? Мол, вместо линейного сравнения первого символа подстроки с каждым символом строки мы сравниваем последний символ подстроки с соответствующим символом строки и движемся вперед большими прыжками. Размер прыжка вычисляем по таблице, которую готовим вначале. Минус - надо готовить таблицу прыжков. Плюс - прыгаем на большие расстояния. Резюме: Для длинных текстов получается значительное ускорение поиска." А потом уже можно переходить к практической части. Ну и "напишем цикл", это как-то совсем для школьников. Вы же алгоритм объясняете, а не программировать учите.
Код это хорошо, расписывание по шагам это прекрасно.
Но раз уж статья про алгоритм, в ней просто обязательно должно быть про асимптотику. Особенно если рассказывается также про оптимизации.
p — ;
2. Также обратите внимание на лишние пробелы. В частности здесь:
return — 1;3. Не хватает:
— Асимптотика (по времени и памяти; для случаев с использованием таблицы смещений, таблицы суффиксов);
— Достоинства и недостатки алгоритма и его эвристик (когда эффективна та или иная эвристика по отдельности, а когда эффективны обе и почему);
— Анализ влияния используемого алфавита, числа символов в строке, числа символов в подстроке на время выполнения (также сравнение с линейным поиском в этом же смысле) — это, скорее всего, на пятерку с плюсом.
4. Название статьи нужно сделать конкретнее. Например, «Алгоритм поиска строки Бойера — Мура».
Тут сказано:
int last = pattern.length — 1;
А дальше в шагах:
t += last — offset[text[t + last]]
t += last — offset[text[0 + 7]]
Но last равен length — 1, то есть 6. Я так понял, надо прибавлять всё таки длину, тогда нужно было писать t + last + 1
Еще для нахождения строки m в строке n можно воспользоваться суффиксным деревом. Само дерево строится за O(n), а поиск осуществляется только за O(m).
Поправьте форматирование кода, плиз.
int[] createOffsetTable(string pattern) { int[] offset = new int[128]; // количество символов зависит от // алфавита с которым мы работаем for (int i = 0; i < prefix.length; i++){ offset[i] = -1; // заполняем базовыми значениями } for (int i = 0; i < pattern.length; i++){ offset[pattern[i]] = i; } return offset; }
а что здесь есть prefix и откуда он появился?
Чтобы пишется вместе.
Найти подстроку в строке