我想创建一个方法来搜索一小段文本（通常不超过 256 个字符）以查找大约 20 个不同单词中的任何一个。如果它在文本中找到一个而不考虑大小写，则返回 true。
该方法将执行相当多（不是疯狂的数量），因此它必须尽可能高效。你建议在这里最好的是什么？
20个字没有变化。它们是静态的。但是要扫描的文本可以。
问问题
186 次
8 回答
5
我建议：将输入文本中的所有单词添加到 a Set- 毕竟它只有 256 个字符，添加它们是一个O(n)操作。
之后，您可以使用 的contains()操作来测试 20 个左右的每个单词的成员资格Set，即O(1).
于 2013-07-31T11:37:46.627 回答
3
由于要搜索的 20 个单词不会改变，因此查找它们的最快方法之一是编译一个匹配它们的正则表达式，然后在不同的输入中重用它。对于不需要回溯的简单正则表达式，将正则表达式与给定字符串匹配的复杂性与字符串长度成线性关系。在你的情况下，长度是有界的，所以它是 O(1)。
于 2013-07-31T11:40:29.157 回答
2
这个String类已经有很多方法来做这些事情。例如，该indexOf方法将解决您的问题：
String str = "blahblahtestblah";
int result = str.indexOf("test");
result如果字符串不包含单词“test”，则将包含 -1。我不确定这对你来说是否足够有效，但我会从这里开始，因为它已经实施了！
于 2013-07-31T11:37:53.550 回答
2
假设这 20 个单词都在 a 中Set<String>并且都是小写的，那么它很简单：
public final boolean containsWord(final String input)
{
final String s = input.toLowerCase();
for (final String word: wordSet)
if (s.indexOf(word) != -1)
return true;
return false;
}
于 2013-07-31T11:39:22.503 回答
1
如果您想同时搜索多个不同的目标，那么Rabin-Karp 算法是一种可能。如果您的 20 个目标列表中只有几个不同的字长，则 if 尤其有效。一次遍历字符串将找到给定长度的所有匹配项。
于 2013-07-31T11:51:08.710 回答
0
您可以将所有单词放到一个列表中，对其进行排序并使用 Collections.binarySearch(...)。你会在排序上松懈，但 binarySearch 是 log(n)。
于 2013-07-31T11:47:34.647 回答
0
我会做以下事情：
String longStr //the string to search into
ArrayList<String> words; //the words to check
Iterator<String> iter = words.iterator();
while(iter.hasNext())
{
if(longStr.contains(iter.next()))
return true;
}
return false;
于 2013-07-31T11:42:20.740 回答