Anyone knows how to solve this question or have any other solutions to solve this question in Python? Develop a program in Python to find the top longest palindromes from a input string.

Currently my code is only able to print out a single longest palindrome:

import sys 
# A utility function to print a
# substring str[low..high]
def printSubStr(st, low, high) :
    sys.stdout.write(st[low : high   1])
    sys.stdout.flush()
    return ''
 
# This function prints the longest palindrome substring of st[]. It also returns the length of the longest palindrome
def longestPalSubstr(st) :
    n = len(st) # get length of input string
    # table[i][j] will be false if substring
    # str[i..j] is not palindrome. Else
    # table[i][j] will be true
    table = [[0 for x in range(n)] for y
                          in range(n)]
     
    # All substrings of length 1 are palindromes
    maxLength = 1
    i = 0
    while (i < n) :
        table[i][i] = True
        i = i   1
     
    # check for sub-string of length 2.
    start = 0
    i = 0
    while i < n - 1 :
        if (st[i] == st[i   1]) :
            table[i][i   1] = True
            start = i
            maxLength = 2
        i = i   1
     
    # Check for lengths greater than 2.
    # k is length of substring
    k = 3
    while k <= n :
        # Fix the starting index
        i = 0
        while i < (n - k   1) :
             
            # Get the ending index of substring from starting index i and length k
            j = i   k - 1
     
            # checking for sub-string from ith index to jth index if st[i   1] to st[(j-1)] is a palindrome
            if (table[i   1][j - 1] and
                      st[i] == st[j]) :
                table[i][j] = True
     
                if (k > maxLength) :
                    start = i
                    maxLength = k
            i = i   1
        k = k   1
    print("Longest palindrome substring is: ")
    print(printSubStr(st, start,start   maxLength - 1))
 
    return maxLength # return length of LPS

#driver code
st = "agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga"
l = longestPalSubstr(st)
print("Length is:\n", l)

CodePudding user response：

Here's a straightforward (although not necessarily optimal) algorithm for finding all of the palindromic substrings within a string. It just iterates through all the substrings and saves the ones that are palindromes.

def get_palindromes(s):
    """
    Return a set of all palindromic substrings of s.
    """
    result = set()
    # Iterate through all possible non-empty substrings
    for start in range(len(s)):
       for end in range(start   1, len(s)   1):
           substring = s[start:end]
           # Is substring a palindrome?
           if substring == substring[::-1]:
               result.add(substring)
    return result

The output on your test string is:

>>> get_palindromes('agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga\\')
{'a', 'g', 's', 'gag', 'ertytre', '2', 'bb', 'k', 'sas', 'w', 't', 'q', 'y', 'r', 'h', 'b', '565', '\\', '1', 'j', 'i', 'e', '45654', '32123', '12345654321', 'wertytrew', 'rtytr', 'aga', 'qwertytrewq', '5', '234565432', 'aa', '3', '6', '4', 'tyt', '3456543', '212'}

Now, you just need to sort these values by length, take the 3 longest ones, find them again within the original string, and print each palindrome, index, and length.

CodePudding user response：

Instead of using maxLength, use a minimum heap maxLengths to store the k maximum lengths encountered till now (k=3 for your example).

Try replacing this:

if (k > maxLength) :
    start = i
    maxLength = k

With something like

# maxLengths is being used as a min heap
maxLengths.push((k, start))
if len(maxLengths) > 3:
    maxLengths.pop()

CodePudding user response：

This uses a list comprehension to get all odd length substrings and then searches them for palindrome with the is_palindrome function building a list of results. Finally the results are sorted and displayed.

EDIT: Added deduping of "sub palindromes" re: Ken's comment. EDIT2: Allow even length palindromes

input_str = "agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga\\"


def is_palendrome(string):
    return string == string[::-1]


subs = [input_str[i: j] for i in range(len(input_str))
        for j in range(len(input_str)   1, i, -1)]

results = []
for sub in subs:
    if is_palendrome(sub) and not any(sub in result['str'] for result in results):
      results.append({'str': sub, 'idx': input_str.index(sub), 'len': len(sub)})
results = sorted(results, key=lambda x: x['len'])[-3::]
for line in results:
    print(f"Palindrome: {line['str']}, Index: {line['idx']}, Length: {line['len']}")