假设我有一组字符串：
Set<String> things = new HashSet<String>();
things.add("coffee cup");
things.add("smartphone");
things.add("inkjet printer");
// :
// list could be quite large (100K or so, perhaps loaded from a database)
// :
现在我想检查另一个字符串是否完全包含上述集合中的任何字符串。所以：
"a coffee cup" - matches
"android smartphone" - matches
"inkjet printer for sale" - matches
"laser printer" - does not match
"printer" - does not match
我能想到的唯一方法是遍历集合（如果找到则中断）。有没有更有效和优雅的方法来做到这一点？
你需要 Aho-Corasick 算法。 http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
https://github.com/raymanrt/aho-corasick
预处理的时间复杂度为 O(m)（其中 m 是集合中字符串的总长度），匹配的时间复杂度为 O(n)（其中 n 是匹配字符串的长度）。所以它是渐近最优的。
遍历候选的所有子字符串，并检查集合是否包含它们？
boolean containsSubstring(Set<String> set, String str) {
for (int i = 0; i < str.length; i++) {
for (int j = i + 1; j < str.length; j++) {
if (set.contains(str.substring(i,j))) {
return true;
}
}
}
return false;
}
是的，长度为 k 的字符串有 k^2 个子字符串，但这可能仍然远远少于集合中的字符串数......
我建立在@meriton 的建议之上。我将做所有可能的单词组合，而不是所有可能的子字符串组合。
Set<String> permutations = new HashSet<String>();
String [] arr = token.split(" ");
int size = arr.length;
for (int i = size ; i > 0; i--) {
for (int j = 0 ; j < i; j++) {
StringBuilder permutation = new StringBuilder();
permutation.append(arr[j]);
for (int k = j+1 ; k < i; k++) {
permutation.append(" ");
permutation.append(arr[k]);
}
permutations.add(permutation.toString());
}
}
如果我通过上面的代码片段运行“出售喷墨打印机”，我会得到：
然后我可以contains()对原来的一组词做一个简单的处理。