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

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。