注意:这个问题与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)
)。然而,到目前为止,我未能将这种方法应用于更一般的子串问题。你知道吗
首先消除所有重复项。通过在迭代数据时使用哈希表并存储已经看到的字符串,这是相当容易做到的。(如果您担心哈希表的最坏情况,可以使用trie或排序和迭代来过滤重复)
过滤掉所有重复项后,为所有剩余字符串创建一个suffix-tree。
在创建后缀树之后,对于每个字符串,检查它是否作为某个字符串的后缀存在,而不是它本身。这是通过沿着后缀树上的路径从根到字符串的结尾来完成的,如果您的唯一选项是完全相同的字符串,那么它不是子字符串(否则-它是)。你知道吗
时间复杂性:
O(n*mlog(m))
中完成的。你知道吗n
字符串是O(nm)总的复杂性是
O(n*mlog(m))
相关问题 更多 >
编程相关推荐