Можно ли изменить алгоритм Бойера-Мура для поиска только "полных слов"?

Question

Я написал функцию Java, которая реализует алгоритм Бойера-Мура для поиска заданной подстроки в массиве символов. Возвращает список каждого индекса, в котором найдена подстрока в массиве. Например, если искомый массив символов содержит фразу "Ходячие мертвецы", а подстрокой, заданной в качестве параметра, является "король", будет возвращен список размера 1, содержащий значение 7.

Я хотел бы изменить эту функцию так, чтобы возвращались только индексы подстрок, которые являются полными словами в массиве char. Таким образом, предыдущий пример вернул бы пустой список, но если подстрока была изменена на "The", "Walking" или "Dead", списки размером 1 были бы возвращены со значениями 0, 4 и 12 соответственно.

Можно ли реализовать такую ​​функциональность с помощью алгоритма Бойера-Мура? Существуют ли какие-либо другие алгоритмы поиска строк, которые могли бы эффективно получать эти результаты?

Answer 1

Это может быть не тот тип ответа, который вы хотите, но вы можете изменить аргументы вместо алгоритма: добавьте пробел в начало и конец вашей строки поиска, а также в начало и конец вашей целевой строки (в случае первое или последнее слово являются хитом). Вам также нужно будет обрабатывать знаки препинания и другие несловарные символы.

Answer 2

Просто используйте шаблон Java - он уже реализует Бойера Мура внутренне. Тогда '\b' соответствует границе слова. Как в:

    Pattern pattern = Pattern.compile("\\b" + Pattern.quote(needle) + "\\b");
    Matcher m = pattern.matcher(haystack);
    while (m.find()) {
        System.out.println(m.start());
    }

Answer 3

Да, вы можете настроить Бойера-Мура, чтобы сделать это:

• После каждого "совпадения" вы можете проверить, что начальная и конечная позиции для совпадения находятся на границах слов.

• Вы изменяете поиск с "king" на "word-border +" king "+ word-border", где "word-border" - это псевдосимвол, который ваш модифицированный BM сопоставляет с любым символом границы слова.

• Вы можете предварительно обработать ввод, чтобы заменить все пробелы, знаки препинания и т. Д. Специальным символом, означающим "граница слова", и затем выполнить поиск по нему.

Что из этого может быть лучше, зависит от того, как вы их реализуете... и собираетесь ли вы многократно искать один и тот же входной текст.