如何做一个有效的检查，如果一个字符串在更大的一组部分地存在？(How to do a efficie

说我有一组字符串：

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

我能想到的是通过一套迭代的唯一方法（和打破-ING如果找到）。是否有一个更有效和更优雅的方式来做到这一点？

Answer 1:

您需要阿霍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是匹配的字符串的长度）。因此，它是渐近最优的。

Answer 2:

遍历候选的所有子，并检查集是否包含他们？

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子，但仍可能远远小于在一组琴弦数...

Answer 3:

我内置关@梅里的建议。相反，每一个可能的子组合，我会做一切可能的文字组合。

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());

    }
}

如果说我的代码片段运行“出售喷墨打印机”上面，我得到：