Во-первых, я не знаю, почему вы для этого используете классы. Мы в python не пишем классы, если не используем OOP, которым вы не являетесь.
Intro
Я прошел через середину, это будут подстроки палиндрома * 1, и с этой середины пошли налево, пока подстрока не перестанет быть палиндромом или конец строки встречен
код
def find_longest_p(s):
pal_start = 0; pal_end = 1 # indexes of longest
for half_index in range(0, len(s)*2-1):
# about 1st range bounds
# it goes over middles of palindromes
# which are at some char or between 2 chars
# that char is s[half_index/2]
# where for odd it is s[x.5] meaning between s[x] a& s[x+1]
c = b = -1 # start with value because for else is asking for b,c
for b in range((half_index + half_index % 2) // 2 - 1, -1, -1):
# starts from first index to the left, goes to 0
# "a b c d" (str "abcd", disregard spaces)
# 0123456 (half indexes)
# for half_index == 4
# b goes -> 1 -> 0
# for half_index == 3
# b goes -> 1 -> 0
c = half_index - b # symetric index of b
if c < len(s) and s[b] == s[c]: # if not, either end of string or no longer palindrome
continue
lenght = c - b - 1
if lenght > pal_end - pal_start:
pal_start = b + 1
pal_end = c
break
else:
# out of bounds to the left
# arithmetic changes a little
lenght = c - b + 1
if lenght > pal_end - pal_start:
pal_start = b
pal_end = c + 1
return s[pal_start : pal_end]
сложность
Кажется, что это O (n ^ 2) что на самом деле не так, поскольку в строке среднее не так много палиндромов. означает, что второй l oop в основном имеет одну итерацию взяв O (n) время сложность, и дополнительный O (1) пробел , определяющий 3 переменные и некоторые промежуточные продукты, или O (n) пробел , если вы включаете копирование и нарезку s (что неизбежно)
Сноски
* 1 середина палиндрома может быть по некоторому индексу или между двумя индексами поэтому я прошел двойные индексы коридоры будут: 0, 0,5, 1, 1,5, ... Я пошел: 0, 1, 2, 3, ...