Создание функции longest_palindrome из функции find_all_palindromes

Question

Я хочу создать функцию, которая печатает самую длинную палиндромную подстроку большого объема текста. Я уже сделал код для поиска всех палиндромов текста. Теперь я хочу, чтобы он печатал только самый длинный. Но это не работает. Может кто-нибудь помочь?

def find_palindrome_substr(string, left, right):
 while left >= 0 and right <len(string):
  if string[left] != string[right]:
   break
  print string[left: right+1]
  left -=1 #expand to left
  right +=1 #expand to right

def find_all_palin(string):
  for i in xrange(0, len(string)):
   find_palindrome_substr(string, i-1, i+1)
   find_palindrome_substr(string, i, i+1)

find_all_palin("aabbbaa")

Как сделать этот код таким, чтобы он печатал только самую длинную подстроку палиндрома? Я работаю в python 3.7

Answer 1

В данный момент вы печатаете все найденные палиндромы. Вместо этого вы хотите сохранить их в списке, чтобы потом можно было проверить, какой из них самый длинный.

def find_palindrome_substr(string, left, right):
  palindromes = list()
  while left >= 0 and right <len(string):
    if string[left] != string[right]:
       break
    palindromes.append(string[left: right+1])
    left -=1 #expand to left
    right +=1 #expand to right
  return palindromes

def find_longest_palin(string):
   all_palindromes = list()
   for i in xrange(0, len(string)):
     all_palindromes.extend(find_palindrome_substr(string, i-1, i+1))
     all_palindromes.extend(find_palindrome_substr(string, i, i+1))

   # get lengths of each palindrome we found
   lengths_palindromes = [len(pal) for pal in all_palindromes]

   # find the index of the longest palindrome
   index_longest_palindrome = lengths_palindromes.index(max(lengths_palindromes))

   # print longest palindrome
   print all_palindromes[index_longest_palindrome]
find_longest_palin("aabbbaa")

Answer 2

Один из способов сделать это - сохранить список. Однако этот список будет хранить только 1 строку в любой момент времени. Поэтому каждый раз, когда вы вызываете find_palindrome_substr(), вы проверяете, является ли вновь созданная строка длиннее, чем строка, которая уже существует в списке. Если это так, замените строку в списке новой. За исключением первого вызова, когда список пуст, вы добавляете к нему слово безоговорочно. Код будет выглядеть примерно так:

def find_palindrome_substr(string, left, right, palinList):
 while left >= 0 and right <len(string):
  if string[left] != string[right]:
   break

  thisPalin = string[left: right + 1] 
  if(len(palinList) == 0):
    palinList.append(thisPalin)
  else:
    if(len(palinList[0]) < len(thisPalin)):
        palinList.pop()
        palinList.append(thisPalin)

  left -=1 #expand to left
  right +=1 #expand to right

def find_all_palin(string):
  palinList = []
  for i in range(0, len(string)):
   find_palindrome_substr(string, i-1, i+1, palinList)
   find_palindrome_substr(string, i, i+1, palinList)

  return palinList[0]

print(find_all_palin("aabbbaa"))

Вывод:

aabbbaa

Answer 3

Я позволил себе изменить print на print() и xrange на range, чтобы он работал на python 3.

Одно решение, которое вы можно использовать, это добавить все палиндромы в список palindromes.append("word"), а затем вычислить их длины с помощью понимания списка и распечатать один из списка с помощью функции max(), которая находит наибольшее значение .

palindromes = []

def find_palindrome_substr(string, left, right):
    while left >= 0 and right <len(string):
        if string[left] != string[right]:
            break
        palindromes.append(string[left: right+1])
        left -=1 #expand to left
        right +=1 #expand to right

def find_all_palin(string):
    for i in range(0, len(string)):
        find_palindrome_substr(string, i-1, i+1)
        find_palindrome_substr(string, i, i+1)
    len_palindromes = [(len(palindrome), palindrome) for palindrome in palindromes]
    print(max(len_palindromes)[1])

find_all_palin("aabbbaa")

Бег производит

aabbbaa