java - 在一组字符串中查找超字符串

Question

我有一个字符串列表，例如：

cargo
cargo pants
cargo pants men buy
cargo pants men
cargo pants men melbourne buy

在此，包含所有剩余字符串的字符串是cargo pants men melbourne buy. 我想删除所有较短的字符串并只保留最长的“超级字符串”。

请注意，如果存在 2 个查询cargo pants并且cargo shorts存在，它们将被视为 2 个不同的查询并且不会合并。

到目前为止，我一直在以蛮力的方式执行此操作 - 从集合中选择一个字符串并遍历同一集合，删除所有其他作为当前字符串“子字符串”的字符串。大致，

for (String p: big_set) {
    for (String q: big_set) {
        if (!p.equals(q)) {
            if (has_all_words(p, q)) { /* If all words in 'p' is also in 'q' */
                big_set.remove(p);
                break;
            }
        }
    }
}

是否有一种智能算法可以在少于 O(n^2) 的时间内做到这一点？在这个函数中，has_all_words比较时会保留单词的顺序。

出于好奇，我有一个包含数十亿搜索查询的庞大列表（例如发送到 Google/Yahoo/Bing 的搜索查询），我正在尝试为这些查询找到上位词。有一个服务器可以解析这个字符串并生成各种有趣的类别。我正在尝试压缩查询列表，以期最小化计算成本和带宽。这种方法肯定会显着减少带宽（因为人类不能一口气想到buy cargo pants melbourne），但预计算成本高得令人望而却步。所以我一直在寻找可以做到这一点的算法，但我还没有遇到任何可以做到这一点的算法。

标签： javastringalgorithmcollections

Answer 1

• 我认为您要要求的只是删除所有可以在超级字符串中找到的子字符串。就像 ["foo bar", "foo baz"] 的情况一样，您必须存储两个字符串。

• 如果我的猜测是正确的，那么您可以在少于 O(n^2) 的时间内实现它。在开始之前按字母顺序排列每个超级字符串，这样就不会像货物裤子裤子货物男士购买这样的情况了

• 
  首先，根据长度对字符串进行降序排序。然后拿起最长字符串的子字符串（因为我们
  从第一个索引迭代并以相反的顺序排序）并
  开始在其余字符串中搜索它。

• 如果找到字符串，则将其删除，并且一旦搜索和删除完成，只需再次使用相同超字符串的下一个子字符串进行迭代，并包含最后一个子字符串。

• 最后，您将只剩下唯一的字符串（如果您将 ["foo bar", "foo baz"] 视为唯一字符串。