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

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;
    }
}

Answer 1

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

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

构造尝试的预处理步骤将在 O(N*L*L) 内完成。

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

Answer 2

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

\n\n

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

\n\n

\n

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

\n

• 遍历哈希表，选取索引不是-1\xe2\x80\x94 的子字符串，这些子字符串是其相应索引的答案，但仅当该名称在上一次迭代中还没有更短的答案时才使用它们

\n

\n\n

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

\n