I am trying to find the solution for finding all subsequent substrings of a given string. But the code I wrote is not that much efficient. Is there any other method with lesser time complexity to solve this problem? I have imported 'combinations' method from the 'itertools' library. I heard there can be a powerset recipe made using chain and combinations, but that method seems to print out all substrings possible which contains the non-subsequent ones also.

Code I tried

from itertools import combinations


test = "abcd"
res = [test[x:y] for x, y in combinations(range(len(test)   1), r = 2)]

print(res)

output:- ['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd']

CodePudding user response：

def x(word):
    s = set()
    for a in range(len(word)):
        for b in range(a,len(word)):
            s.add(word[a:b 1])
    return s
x("abcd")

>>>
{'a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd'}

Time taken: 0.0009999275207519531

I tested the run time for your code, and it gave 0.0010001659393310547, meaning this solution is slightly more efficient.

CodePudding user response：

Just use two nested loops, generating combinations is extremely inefficient to solve this problem:

test = "abcd"
print([test[i:j   1] for i in range(len(test)) for j in range(i, len(test))])

Output:

['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd']