获取给定字符串的唯一子字符串列表

Question

任务是获取Python中唯一的子字符串列表。

我目前将问题分为两部分：获取所有子字符串的列表，然后获取唯一的子字符串。

我正在使用以下代码：

substrings=[]
for i in range(0,len(inputstring)+1):
    for j in range(i+1,len(inputstring)+1):
        substr=inputstring[i:j]
        substrings.append(substr)
uniq=[]
for ss in substrings:
    if ss not in uniq:
        uniq.append(ss)

是否有更快的方法来解决这个问题，或者所谓的Python方法以更灵活的方式来解决这个问题？

一个简单的示例字符串是：

"aabaa"

，可能的子字符串是

[a,a,b,a,a,aa,ab,ba,aa,aab,aba,baa,aaba,abaa,aabaa]

，最后需要的唯一子字符串

[a,b,aa,ab,ba,aab,aba,baa,aaba,abaa,aabaa]

Answer 1

使用 Itertools 和 Set。与 Edwin 的答案类似，但使用 Itertools，并且在一行中。

import itertools

uniq=list(set([inputstring[x:y] for x, y in itertools.combinations(
            range(len(inputstring) + 1), r = 2)]))

基本上，您使用 itertools 首先查找所有组合，然后设置查找唯一元素，然后转换为列表。

组合代码取自https://www.geeksforgeeks.org/python-get-all-substrings-of-given-string/

编辑以获得更清晰的解释： 首先，使用组合来获取子字符串对应的所有索引对。这里的技巧是 itertools.combinations 从所有 (0,X) 对开始，然后是 (1,X) 对，等等。由于我们使用的是组合而不是排列，因此我们消除了反向子字符串，例如 (1,0)因为它们将在 (0,X) 枚举中看到。

然后简单地将它们与列表理解一起使用来获取所有子字符串，使用集合来查找唯一元素，然后转换为列表。

希望有帮助

Answer 2

第二部分使用集合而不是列表。在列表中查找某项的成本为 O(n)，而在集合中查找某项的成本为 O(1)，并且您不必检查它是否是新的。如果列表中已有内容，集合将不会添加该内容。

uniq=set()
for i in range(0,len(inputstring)+1):
    for j in range(i+1,len(inputstring)+1):
        substr=inputstring[i:j]
        uniq.add(substr)