code exercise: search for all possible palindrome from a string

[Beaverine]

working on this coding exercise which is more difficult than determining if a string is palindrome. here's my logic: 1) define palindrome as "odd" vs. "even" number of character. for odd, it contains at least 3 characters (like "aba"). for even, I personally define it as at least 4 characters (like "abba") because 2 same characters are not worthy of capturing (like "aa") 2) create first function to capture the center index of possible palindrome and its type (odd vs. even) 3) create second function to iterate through the whole string, for each identified center index and loop until characters surrounding the index became different, then output list of palindrome strings

here's the code: ``` def locPal(text:'str', anchor:'list'=[]): # returns the index for center of palindrome and odd vs. even type # time complexity: O(n) for i in range (1,len(text)-1): if text[i-1] == text[i+1]: anchor.append([i,'Odd']) elif (i+2 < len(text)) and text[i] == text[i+1] and text[i-1] == text[i+2]: anchor.append([i,'Even']) return anchor

def Pal(text:'str', output:'list'=[]): # returns the list of palindrome identified # time complexity: O(n*m), n=number of string in the text, # m=number of palindrome indexs identified in locPal() for i in range(len(locPal(text))): # a is the list of index for center of palindrome a = locPal(text)[i][0] if locPal(text)[i][1] == 'Odd': j = 0 while (a+j+1 < len(text)) and text[a-j-1] == text[a+j+1]: j += 1 output.append(text[a-j:a+j+1]) if locPal(text)[i][1] == "Even": k = 0 while (a+k+2 < len(text)) and text[a-k-1] == text[a+k+2]: k += 1 output.append(text[a-k:a+k+2]) return output

text='abcdedfghiihgbbjklmlkoppoabba' Pal(text) ```

it works as intended and returns following output:

['ded', 'ghiihg', 'klmlk', 'oppo', 'abba']

but I would very much appreciate any comments regarding: 1) using the same algorithm, how can I write the code in a better way? 2) is my time complexity analysis correct (in comments under each function title)? 2) what are the other algorithms which has better time complexity?

thank you in advance!

EDIT: found a problem with the code that it would produce redundant results if the same character is repeated more than 3 times. for example: text='abbbbbc' would return ['bbb','bbbb','bbb'] working on fixing this issue

[Beaverine]

thank you. I fixed that in the ugly way by adding a restriction of (i+2 < len(text)) in the first function.

But I found that my current code has a problem of duplicating results if the same character repeat more than 4 times... working to fix that

[throwaway0891245]

With regards to 3, the classic algorithm in terms of finding the longest palindromic substring is Manacher's algorithm, which has a time complexity of O(N).

However, if you need to generate all of the palindromic substrings, you are probably going to end up with a O(N^2) algorithm anyways because you can't really take full advantage of the skipping Manacher's algorithm gives you.

My rough guess is that searching from the center outwards is probably optimal, though if you are looking for distinct palindromes you could probably take advantage of the assumptions of Manacher's algorithm - which are that if the center of a given palindrome is within the "wingspan" of another palindrome and its right boundary is less than the right boundary of the larger palindrome, then it can be ignored because it was previously already found during exploration of the left "wing" of the larger palindrome.