是否可以将Boyer-Moore算法修改为仅搜索“完整单词”？

Question

我已经编写了一个Java函数，它实现了Boyer-Moore算法来在char数组中搜索给定子字符串。它返回在数组中找到子字符串的每个索引的列表。例如，如果要搜索的字符数组包含短语"The Walking Dead“，并且作为参数给定的子字符串是"king"，则将返回一个包含值7的大小为1的列表。

我想更改此函数，以便只返回char数组中完整单词的子字符串的索引。因此，前面的示例将返回一个空列表，但是如果将子字符串更改为" the“、"Walking”或"Dead"，则大小为1的列表将分别返回值为0、4和12。

这种功能可以使用Boyer-Moore算法实现吗？有没有其他的字符串搜索算法能够高效地产生这些结果？

Answer 1

这可能不是您想要的那种答案，但您可以更改参数而不是算法:在搜索字符串的开头和结尾以及目标字符串的开头和结尾添加一个空格(以防第一个或最后一个单词是命中的单词)。您还需要特别对待标点符号和其他非单词字符。

Answer 2

是的，你可以调整Boyer-Moore来做到这一点：

单词边界每次“匹配”后，您可以检查匹配的开始和结束位置是否在单词边界将搜索从“”更改为“word -

• + "king”+word- boundaries.
• You“，其中”word-
• “是一个伪字符，您的修改后的B-M将其与任何单词边界字符进行匹配。
• 您可以对输入进行预处理，将所有空格、标点符号等替换为表示”单词边界“的特殊字符，然后进行搜索。

其中哪一个可能更好取决于您如何实现它们……以及您是否要重复搜索相同的输入文本。

Answer 3

只需使用Java的Pattern -它已经在内部实现了Boyer Moore。然后'\b‘匹配一个词边界。如下所示：

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