在一个数组中找到每个字符串的最小唯一子串

Question

(我是在JavaScript环境下编写这篇文章的，但我会接受任何语言中算法正确的答案)

如何查找字符串数组中每个元素的最短子串，其中该子串不包含在其他元素中（忽略大小写）？

假设我有一个输入数组，例如：

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];

输出应该类似于：

var uniqueNames = ["ne", "h", "ua", "ka", "i", "r"];

就我的目的而言，你可以安全地假设没有元素完全包含在另一个元素中。

我的想法：
看起来可以采用暴力方法，按照以下方式进行：

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
var uniqueNames = [], nameInd, windowSize, substrInd, substr, otherNameInd, foundMatch;
// For each name
for (nameInd = 0; nameInd < names.length; nameInd++)
{
    var name = names[nameInd];
    // For each possible substring length
    windowLoop:
    for (windowSize = 1; windowSize <= name.length; windowSize++)
    {
        // For each starting index of a substring
        for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++)
        {
            substr = name.substring(substrInd,substrInd+windowSize).toLowerCase();
            foundMatch = false;
            // For each other name
            for (otherNameInd = 0; otherNameInd < names.length; otherNameInd++)
            {
                if (nameInd != otherNameInd && names[otherNameInd].toLowerCase().indexOf(substr) > -1)
                {
                    foundMatch = true;
                    break;
                }
            }

            if (!foundMatch)
            {
                // This substr works!
                uniqueNames[nameInd] = substr;
                break windowLoop;
            }
        }
    }
}

但我想象中应该有一种更优雅的解决方案，可以使用字典树/前缀树、后缀数组或像那样有趣的东西。

编辑： 我认为以下是JavaScript中所选答案的程序形式：

var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
var uniqueNames = [], permutations = {}, permutation, nameInd, windowSize, substrInd, substr;

// For each name
for (nameInd = 0; nameInd < names.length; nameInd++)
{
    var name = names[nameInd];
    // For each possible substring length
    windowLoop:
    for (windowSize = 1; windowSize <= name.length; windowSize++)
    {
        // For each starting index of a substring
        for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++)
        {
            substr = name.substring(substrInd,substrInd+windowSize).toLowerCase();
            permutations[substr] = (typeof permutations[substr] === "undefined")?nameInd:-1;
        }
    }
}

for (substr in permutations)
{
    permutation = permutations[substr];
    if (permutation !== -1 && ((typeof uniqueNames[permutation] === "string" && substr.length < uniqueNames[permutation].length) || typeof uniqueNames[permutation] === "undefined"))
    {
        uniqueNames[permutation] = substr;
    }
}

- Patrick

---

你的样例输出有误吗？我在其中没有看到s和y，但是我看到了i、h和r... - Icarus

@Icarus 啊，说得好。s和y之所以不在其中，只是因为我不是在寻找符合条件的所有最小子字符串，而是任何一个都可以。如果有人能够返回一个包含它们所有的二维数组作为答案，我也会接受，但我并不需要那么详细的信息。同样有效的输出可能是`var uniqueNames = ["ne", "y", "ua", "ka", "i", "s"];` - Patrick

你是否可以将输入字母限制在26个字符以内（或类似的方式，只是限制一下）？ - Saeed Amiri

@SaeedAmiri 我不太确定你的具体方向是什么，但我的实际输入仅包含 [0-9a-zA-Z_-'&,.\s] 字符，您可以将输出限制为仅包含字母数字字符，虽然我可能会选择更少限制的答案而不是更多的答案，你懂的？ - Patrick

@Patrick，有一种使用后缀数组的O(M)解决方案；其中M是所有字符串长度的总和。 - bloops

我相信这个问题最多可以用O(N^2)的时间复杂度解决，最坏情况下是O(L*N^2)。但是我强烈怀疑可以用O(N^1.5)甚至O(N log N)的时间复杂度来解决。 - RBarryYoung

Answer 1

这个问题可以在 O(N*L*L*L) 的复杂度内解决。方法是使用后缀字典树。字典树的每个节点还将存储前缀计数，表示从根到该节点遍历形成的子串在所有插入至今的后缀中出现的次数。

我们将构建 N+1 个字典树。第一个字典树是全局的，我们将其用于插入所有 N 个字符串的后缀。接下来的 N 个字典树将是本地的，分别包含对应字符串的后缀。

这个构建字典树的预处理步骤将在 O(N*L*L) 内完成。

现在一旦字典树构建完成，我们就可以开始查询每个字符串中子串（从最小长度开始）在全局字典树和对应字符串的字典树中出现的次数。如果两者相同，则意味着它不包含在任何其他字符串中，除了自己。这可以在 O(N*L*L*L) 内实现。复杂度可以解释为，对于每个字符串要花费 N 的时间，L*L 考虑每个子串，L 执行字典树查询。

- Mukesh

---

我认为你所说的“后缀”应该是“子字符串”。 - Mike

Answer 2

如果构建一个广义后缀树，只需要找到每个字符串的中缀从其他字符串的中缀分支出的最浅点，并取该分支点的标签加上一个“区别”字符。关键是必须有这样一个额外的字符（它可能仅在每个字符串末尾附加的元字符处分支），并且分支点可能不会导致叶子节点，它可能导致具有来自同一字符串的所有叶子节点的子树（因此必须考虑内部节点）。

对于每个字符串S，找到仅包含来自S的叶子节点的最浅节点N（按父标签深度），其边缘标签至少包含一个字符。 从根到N的父节点的路径标签，再加上指向N的边缘标签中的一个字符，就是未在其他字符串中找到的S的最短中缀。

我认为仅包含来自一个字符串的节点的标记可以在构建期间完成或通过对GST进行O（N）扫描完成；然后很容易扫描最终的树并为每个字符串保持运行最小值。所以全部都是O（N）。

（编辑-我还不能回复评论）

为了澄清，后缀树中的每个后缀都有一个节点，其中它从其他后缀分支出；这里的目标是找到每个字符串的/ a后缀，该后缀从其他所有字符串的后缀中分支出，以最小深度（由到该节点的路径标签测量）。我们只需要在该点之后再加上一个额外的字符，就可以得到在任何其他字符串中都没有出现的子字符串。

例子：

字符串：abbc，abc

使用Ukonnen算法，在第一个字符串之后，我们只有该字符串的后缀树；我将它们标记为[1]。

abbc[1]
b
 bc[1]
 c[1]
c[1]

下一步，我们插入字符串2的后缀：

ab
  bc[1]
  c[2]
b
 bc[1]
 c
  [1]
  [2]
c
 [1]
 [2]

现在我们想要找到最短的字符串，使得它导向一个只有[1]的分支；我们可以通过扫描所有[1]并查看它们的直接父节点来实现这一点，我会按路径标签列出它们的父节点，再加上一个字符（下面会用到）：

abbc:  abb
bbc: bb
bc: bc[1]
c: c[1]

请注意，我已经包含了 [1]，因为它是区分 [1] 和 [2] 相同后缀的元字符。 当识别在多个字符串中重复的子字符串时，这很方便，但对于我们的问题没有用处，因为如果我们删除 [1]，我们会得到一个同样出现在 [2] 中的字符串，也就是说它不是一个候选项。

现在，右侧的标签都不出现在任何其他字符串中，所以我们选择最短的不包含元字符的标签，即 bb。

类似地，第二个字符串有以下候选项:

abc: abc
bc: bc[2]
c: c[2]

只有一个字符串结尾没有元字符，所以我们采用 abc。

最后一点是这种基于字符串的最小值查找不必逐个执行。可以扫描 GST 一次来标记节点是否包含来自一个字符串（[1]、[2]、..[n]）的叶子，或者为“混合”。然后也可以一次性计算每个字符串的最小非共享字符串（我会称这些为“区分中缀”）。

- KWillets

---

这听起来像是我想象中可能存在的有趣方法，但我仍然没有完全想象出这会是什么样子。我能麻烦您添加一些伪代码或算法步骤吗？如果我能理解如何将其转换为O(N)，我肯定会选择这个答案。 - Patrick

这是同一算法的另一种解释：https://www.reddit.com/r/algorithms/comments/372egn/if_i_have_a_list_of_n_unique_but_similar_strings/crjd6il - OmnipotentEntity

Answer 3

说 N 是字符串的数量，L 是字符串的最大长度。您最多执行 N*L*L*N 次迭代。

我可以通过使用额外的内存来减少一次迭代。对于每个可能的子字符串长度（L 次迭代）：

• 枚举每个名称中该长度的所有子字符串（N*L），并将其存储在哈希表中，其中包括名称的索引 (1)。如果该子字符串已经有一个索引，那么您就知道它不起作用，然后将索引替换为某个特殊值，如 -1。

• 遍历哈希表，挑选索引不是 -1 的子字符串 - 这些是相应索引的答案，但仅在这些名称没有从前一个迭代中获得更短的答案时才使用它们。

可以通过将引用存回现有字符串而不是复制子字符串来大大减少内存使用。

- hamstergene

---

由于似乎没有人提出与最初提供的暴力算法完全不同的算法，因此我将接受这个答案作为更明确定义的改进建议。 - Patrick

尽管如此，我稍微不同意你的大O估计。由于indexOf是在L上进行迭代操作，因此我认为原始暴力算法更像是O(N*L*L*N*L)。因此，删除最后的N*L，改为迭代原始数组所有元素的所有可能排列的哈希表，似乎只是稍微好一点。但是，通过使用canary数组，迭代的数组可以更小。 - Patrick

Answer 4

   for(String s : strArr) { //O(n)
      //Assume the given string as shortest and override with shortest
       result.put(s, s);   
       for(int i = 0; i < s.length(); i++) { // O(m)              
          for (int j = i + 1; j <=s.length(); j++) {
               String subStr = s.substring(i, j);
               boolean isValid = true;
               for(String str2: strArr) { // O(n)
                   if(str2.equals(s)) // Same string cannot be a substring
                     continue;
                     
                    if(str2.contains(subStr)) {
                        isValid = false;
                        break;
                    }
               }

               if(isValid && subStr.length() < result.get(s).length()) 
                   result.put(s, subStr);
           }
        } 
   } 
    
   return result;

- Rohit Katta