12

（我在 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;
    }
}
4

4 回答 4

4

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

我们将构建N+1次尝试。第一个 trie 将是全局的，我们会将所有N字符串的所有后缀插入其中。对于包含相应后缀的N个字符串中的每一个，接下来的N次尝试都是本地的。

这个构建尝试的预处理步骤将在O(N*L*L) 中完成。

现在一旦构建了尝试，对于每个字符串，我们可以开始查询子字符串（从最小长度开始）在全局 trie 和对应于该字符串的 trie 中出现的次数。如果两者都相同，则意味着它不包含在除自身之外的任何其他字符串中。这可以在O(N*L*L*L)中实现。复杂度可以解释为每个字符串的 N，考虑每个子字符串的 L*L，以及在 trie 中执行查询的 L。

于 2013-08-28T05:13:04.947 回答
3

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

对于每个字符串 S，找到最浅的（按父标签深度）节点 N，它只包含来自 S 的叶子，并且其边缘标签包含至少一个字符。从根到 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]) 或“混合”的叶子，然后是每个字符串的最小非共享字符串（我会将这些称为“区分中缀”）也可以一次性计算出来。

于 2015-05-24T14:06:48.953 回答
2

说N是字符串的数量，是字符串L的最大长度。你正在做N*L*L*N迭代。

我只能通过用一次迭代换取额外的内存来稍微改进它。对于每个可能的子串长度（L迭代），

  • 枚举每个名称 ( N*L) 中该长度的所有子字符串，并将其与名称的索引一起存储到哈希表 ( 1) 中。如果这个子字符串已经有一个索引，你知道它不起作用，那么你用一些特殊值替换索引，比如-1.

  • 遍历哈希表，获取索引不存在的子字符串-1——这是它们对应索引的答案，但只有在该名称在前一次迭代中没有更短的答案时才使用它们

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

于 2012-07-01T08:52:55.713 回答
-1 
   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;
于 2021-05-23T16:57:39.200 回答