Given a string, print all the possible substrings which are also the prefix of the given string. Examples:
Input : ababc
Output : a, ab, aba, abab, ababc, a, ab
Input : abdabc
Output : a, ab, abd, abda, abdab, abdabc, a, ab
Approach: We use two variables: start and end to keep track of the current substring and follow the below conditions until start < len(string):
- If the current substring is also the prefix of the given string, print it and increment end. If end == len(string), increment start and end = start
- Else increment start and end = start
Logic to check if the current substring is a prefix of the given string:
string[end] == string[end-start]
This makes use of the fact that if a substring of length L is a prefix of the given string, then the substring of length L+1 obtained after including the next character ch in the sequence is also a prefix of the given string if the character at (L+1) index in the string is equal to ch. Below is the implementation of the above approach:
Python3
# Python3 code to find all possible substrings that # are also the prefix of the given string # Function to print all the special substringsdef func(string): # Used to store the starting and # ending index of the substrings start, end = 0, 0 while start < len(string): # If substring is also the prefix if string[end] == string[end-start]: # Print the substring print(string[start:end + 1], end= " ") end += 1 if end == len(string): start += 1 end = start # Increment the starting # index of the substring else: start += 1 end = start if __name__ == "__main__": string = "ababc" func(string) |
a ab aba abab ababc a ab
Time Complexity: 
Approach: Using a sliding window:
This approach generates all possible substrings of the given string with a given window size and prints them if they are prefixes of the given string. It does this by iterating through the string with a sliding window of size 1 to n and checking if the current substring is equal to the prefix of the given string with the same length. If it is, the substring is printed. This ensures that only prefix substrings are considered.
Python3
def func(string): # initialize the window size to 1 window_size = 1 while window_size <= len(string): # iterate through the string with the current window size for i in range(len(string) - window_size + 1): # check if the current substring is a prefix of the given string if string[i:i+window_size] == string[:window_size]: # print the current substring print(string[i:i+window_size]) # increase the window size window_size += 1if __name__ == "__main__": string = "ababc" func(string)#This code is contributed by Edula Vinay Kumar Reddy |
a a ab ab aba abab ababc
Time complexity: This approach has a time complexity of O(n^2), since we iterate through the string with a window size of 1 to n, and for each iteration, we perform a constant number of operations.
Auxiliary Space: The space complexity is O(1), since we only store a few variables.
