Python program for printing substrings that prefix a given string

Examples :

  Input:  ababc  Output:  a, ab, aba, abab, ababc, a, ab  Input:  abdabc  Output:  a, ab, abd, abda, abdab, abdabc, a, ab 

We use two variables start and end to keep track of the current substring and follow the conditions below until start & lt; len (string) :

  • If the current substring is also a prefix of the given string, print it and increment it. If end == len (string) , increment and end = start
  • Another increment and end = start

Logic to check if the current substring is a prefix of a given string:

 string [end] == string [end-start] 

This uses that the fact that if a substring of length L is a prefix of this string, then a substring of length L + 1, obtained after including the next character in the sequence is also a prefix of this string, if the character in (L + 1) the index per line is.

The implementation of the above approach is shown below:

# Python3 code to find all possible substrings that
# are also a prefix of the given string

# Function to print all special substrings

def func (string):


# Used to store leading and

  # ending index of substrings

start, end = 0 , 0


while start & lt;  len (string):


# If the substring is also a prefix

if string [end] = = string [end - start]:


  # Print substring

print (string [start: end + 1 ] , end = "" )

  end + = 1


if end = = len (string):

  start + = 1

end = start


# Increase start

# substring index

  else :

  start + = 1

end = start


if __ name__ = = " __ main__ " :


string = "ababc"

func (string)

Exit :

 a ab aba abab aba bc a ab 

Time complexity: