从字符串数组中删除子字符串的最有效方法

Question

注意：这个问题与Python无关。我只是用它来代替这里的伪代码。

给定一个数组A包含平均长度为M的N字符串，我想创建一个新的数组B，它只包含A中那些不是A中任何其他字符串的子字符串（或相同副本）的字符串。举个例子：

A = [ 'foo', 'bar', 'foobar', 'foobar' ]
B = [ 'foobar' ]

我特别在寻找最有效的方式来做这方面的时间复杂性。天真的方法看起来是这样的

B = []
for i in range(0, len(A)):
    noSubstring = True
    for j in range(i + 1, len(A)):
        if A[i] in A[j]:
            noSubstring = False
            break
    if noSubstring:
        B.append(A[i])

时间复杂度为O(N^2 * M^2)。我能做些什么来加快速度吗？你知道吗

我一直在考虑使用专用的数据结构来有效地编码和重用字符串序列。例如，如果我想删除只是数组中另一个字符串前缀的字符串，我可以创建一个trie/前缀树（O(N*M)），然后收集所有的叶元素（另一个O(N*M)）。然而，到目前为止，我未能将这种方法应用于更一般的子串问题。你知道吗

Answer 1

首先消除所有重复项。通过在迭代数据时使用哈希表并存储已经看到的字符串，这是相当容易做到的。（如果您担心哈希表的最坏情况，可以使用trie或排序和迭代来过滤重复）

过滤掉所有重复项后，为所有剩余字符串创建一个suffix-tree。
在创建后缀树之后，对于每个字符串，检查它是否作为某个字符串的后缀存在，而不是它本身。这是通过沿着后缀树上的路径从根到字符串的结尾来完成的，如果您的唯一选项是完全相同的字符串，那么它不是子字符串（否则-它是）。你知道吗

时间复杂性：

• 过滤重复：O（n*m）
• 在理论上建立后缀树O（n*m），但实际上是在O(n*mlog(m))中完成的。你知道吗
• 检查每个字符串是O（m），重复检查n字符串是O（nm）

总的复杂性是O(n*mlog(m))