Python：搜索单词中最长的回文和单词/字符串中的回文

Python: search longest palindromes within a word and palindromes within a word/string

提问by user2290820

So here is a code i have written to find palindromes within a word (To check if there are palindromes within a word including the word itself) Condition: spaces inbetween characters are counted and not ignored Example: A but tuba is a palindrome but technically due to spaces involved now it isn't. so that's the criteria.

所以这里是我写的一个代码来查找一个单词中的回文（检查一个单词中是否有回文，包括单词本身）条件：计算字符之间的空格而不是忽略示例：A但大号是回文，但技术上应该现在涉及的空间不是。所以这就是标准。

Based on above, the following code usually should work. You can try on your own with different tests to check out if this code gives any error.

基于以上，下面的代码通常应该可以工作。您可以自己尝试不同的测试，以检查此代码是否有任何错误。

def pal(text):
    """

    param text: given string or test
    return: returns index of longest palindrome and a list of detected palindromes stored in temp
    """
    lst = {}
    index = (0, 0)
    length = len(text)
    if length <= 1:
        return index
    word = text.lower()  # Trying to make the whole string lower case
    temp = str()
    for x, y in enumerate(word):
        # Try to enumerate over the word
        t = x
        for i in xrange(x):
            if i != t+1:
                string = word[i:t+1]
                if string == string[::-1]:
                    temp = text[i:t+1]
                    index = (i, t+1)
                    lst[temp] = index
    tat = lst.keys()
    longest = max(tat, key=len)
    #print longest
    return lst[longest], temp

And here is a defunct version of it. What I mean is I have tried to start out from the middle and detect palindromes by iterating from the beginning and checking for each higher and lower indices for character by checking if they are equal characters. if they are then i am checking if its a palindrome like a regular palindrome check. here's what I have done

这是它的一个不复存在的版本。我的意思是我试图从中间开始并通过从头开始迭代并通过检查字符是否相等来检查字符的每个较高和较低的索引来检测回文。如果是，那么我正在检查它是否像常规回文检查一样是回文。这是我所做的

def pal(t):
    text = t.lower()
    lst = {}
    ptr = ''
    index = (0, 0)
    #mid = len(text)/2
    #print mid
    dec = 0
    inc = 0
    for mid, c in enumerate(text):
        dec = mid - 1
        inc = mid + 1
        while dec != 0 and inc != text.index(text[-1]):
            print 'dec {}, inc {},'.format(dec, inc)
            print 'text[dec:inc+1] {}'.format(text[dec:inc+1])
            if dec<0:
                dec = 0
            if inc > text.index(text[-1]):
                inc = text.index(text[-1])
            while text[dec] != text[inc]:
                flo = findlet(text[inc], text[:dec])
                fhi = findlet(text[dec], text[inc:])
                if len(flo) != 0 and len(fhi) != 0 and text[flo[-1]] == text[fhi[0]]:
                    dec = flo[-1]
                    inc = fhi[0]
                    print ' break if'
                    break
                elif len(flo) != 0 and text[flo[-1]] == text[inc]:
                    dec = flo[-1]
                    print ' break 1st elif'
                    break
                elif len(fhi) != 0 and text[fhi[0]] == text[inc]:
                    inc = fhi[0]
                    print ' break 2nd elif'
                    break
                else:
                    dec -= 1
                    inc += 1
                    print ' break else'
                    break
            s = text[dec:inc+1]
            print ' s {} '.format(s)
            if s == s[::-1]:
                index = (dec, inc+1)
                lst[s] = index
            if dec > 0:
                dec -= 1
            if inc < text.index(text[-1]):
                inc += 1
    if len(lst) != 0:
        val = lst.keys()
        longest = max(val, key = len)
        return lst[longest], longest, val
    else:
        return index

findlet() fun:

findlet() 乐趣：

def findlet(alpha, string):
    f = [i for i,j in enumerate(string) if j == alpha]
    return f

Sometimes it works:

有时它有效：

pal('madem')
dec -1, inc 1,
text[dec:inc+1] 
 s m 
dec 1, inc 3,
text[dec:inc+1] ade
 break 1st elif
 s m 
dec 2, inc 4,
text[dec:inc+1] dem
 break 1st elif
 s m 
dec 3, inc 5,
text[dec:inc+1] em
 break 1st elif
 s m 
Out[6]: ((0, 1), 'm', ['m'])

pal('Avid diva.')
dec -1, inc 1,
text[dec:inc+1] 
 break 2nd if
 s avid div 
dec 1, inc 3,
text[dec:inc+1] vid
 break else
 s avid  
dec 2, inc 4,
text[dec:inc+1] id 
 break else
 s vid d 
dec 3, inc 5,
text[dec:inc+1] d d
 s d d 
dec 2, inc 6,
text[dec:inc+1] id di
 s id di 
dec 1, inc 7,
text[dec:inc+1] vid div
 s vid div 
dec 4, inc 6,
text[dec:inc+1]  di
 break 1st elif
 s id di 
dec 1, inc 7,
text[dec:inc+1] vid div
 s vid div 
dec 5, inc 7,
text[dec:inc+1] div
 break 1st elif
 s vid div 
dec 6, inc 8,
text[dec:inc+1] iva
 break 1st elif
 s avid diva 
dec 8, inc 10,
text[dec:inc+1] a.
 break else
 s va. 
dec 6, inc 10,
text[dec:inc+1] iva.
 break else
 s diva. 
dec 4, inc 10,
text[dec:inc+1]  diva.
 break else
 s d diva. 
dec 2, inc 10,
text[dec:inc+1] id diva.
 break else
 s vid diva. 
Out[9]: ((0, 9), 'avid diva', ['avid diva', 'd d', 'id di', 'vid div'])

And based on the Criteria/Condition i have put:

根据我提出的标准/条件：

pal('A car, a man, a maraca.')
dec -1, inc 1,
text[dec:inc+1] 
 break else
 s  
dec -1, inc 3,
text[dec:inc+1] 
 s a ca 
dec 1, inc 3,
text[dec:inc+1]  ca
 break if
 s a ca 
dec 2, inc 4,
text[dec:inc+1] car
 break else
 s  car, 
dec 3, inc 5,
text[dec:inc+1] ar,
 break else
 s car,  
dec 1, inc 7,
text[dec:inc+1]  car, a
 break 1st elif
 s a car, a 
dec 4, inc 6,
text[dec:inc+1] r, 
 break 1st elif
 s  car,  
dec 5, inc 7,
text[dec:inc+1] , a
 break 1st elif
 s ar, a 
dec 2, inc 8,
text[dec:inc+1] car, a 
 break 1st elif
 s  car, a  
dec 6, inc 8,
text[dec:inc+1]  a 
 s  a  
dec 5, inc 9,
text[dec:inc+1] , a m
 break else
 s r, a ma 
dec 3, inc 11,
text[dec:inc+1] ar, a man
 break else
 s car, a man, 
dec 1, inc 13,
text[dec:inc+1]  car, a man, 
 s  car, a man,  
dec 7, inc 9,
text[dec:inc+1] a m
 break else
 s  a ma 
dec 5, inc 11,
text[dec:inc+1] , a man
 break else
 s r, a man, 
dec 3, inc 13,
text[dec:inc+1] ar, a man, 
 break if
 s   
dec 8, inc 10,
text[dec:inc+1]  ma
 break if
 s  
dec 6, inc 4,
text[dec:inc+1] 
 break 1st elif
 s r 
dec 3, inc 5,
text[dec:inc+1] ar,
 break else
 s car,  
dec 1, inc 7,
text[dec:inc+1]  car, a
 break 1st elif
 s a car, a 
dec 9, inc 11,
text[dec:inc+1] man
 break else
 s  man, 
dec 7, inc 13,
text[dec:inc+1] a man, 
 break if
 s  
dec 5, inc 2,
text[dec:inc+1] 
 break 1st elif
 s c 
dec 1, inc 3,
text[dec:inc+1]  ca
 break if
 s a ca 
dec 10, inc 12,
text[dec:inc+1] an,
 break 1st elif
 s , a man, 
dec 4, inc 13,
text[dec:inc+1] r, a man, 
 break 1st elif
 s  car, a man,  
dec 11, inc 13,
text[dec:inc+1] n, 
 break 1st elif
 s  man,  
dec 7, inc 14,
text[dec:inc+1] a man, a
 s a man, a 
dec 6, inc 15,
text[dec:inc+1]  a man, a 
 s  a man, a  
dec 5, inc 16,
text[dec:inc+1] , a man, a m
 break else
 s r, a man, a ma 
dec 3, inc 18,
text[dec:inc+1] ar, a man, a mar
 break else
 s car, a man, a mara 
dec 1, inc 20,
text[dec:inc+1]  car, a man, a marac
 break else
 s a car, a man, a maraca 
dec 12, inc 14,
text[dec:inc+1] , a
 break 1st elif
 s an, a 
dec 9, inc 15,
text[dec:inc+1] man, a 
 break if
 s  
dec 7, inc 2,
text[dec:inc+1] 
 break 1st elif
 s c 
dec 1, inc 3,
text[dec:inc+1]  ca
 break if
 s a ca 
dec 13, inc 15,
text[dec:inc+1]  a 
 s  a  
dec 12, inc 16,
text[dec:inc+1] , a m
 break 1st elif
 s man, a m 
dec 8, inc 17,
text[dec:inc+1]  man, a ma
 break 1st elif
 s a man, a ma 
dec 6, inc 18,
text[dec:inc+1]  a man, a mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 14, inc 16,
text[dec:inc+1] a m
 break 1st elif
 s man, a m 
dec 8, inc 17,
text[dec:inc+1]  man, a ma
 break 1st elif
 s a man, a ma 
dec 6, inc 18,
text[dec:inc+1]  a man, a mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 15, inc 17,
text[dec:inc+1]  ma
 break 1st elif
 s a ma 
dec 13, inc 18,
text[dec:inc+1]  a mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 16, inc 18,
text[dec:inc+1] mar
 break 1st elif
 s r, a man, a mar 
dec 3, inc 19,
text[dec:inc+1] ar, a man, a mara
 s ar, a man, a mara 
dec 2, inc 20,
text[dec:inc+1] car, a man, a marac
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 17, inc 19,
text[dec:inc+1] ara
 s ara 
dec 16, inc 20,
text[dec:inc+1] marac
 break 1st elif
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 18, inc 20,
text[dec:inc+1] rac
 break 1st elif
 s car, a man, a marac 
dec 1, inc 21,
text[dec:inc+1]  car, a man, a maraca
 break 1st elif
 s a car, a man, a maraca 
dec 19, inc 21,
text[dec:inc+1] aca
 s aca 
dec 21, inc 23,
text[dec:inc+1] a.
 break else
 s ca. 
dec 19, inc 23,
text[dec:inc+1] aca.
 break else
 s raca. 
dec 17, inc 23,
text[dec:inc+1] araca.
 break else
 s maraca. 
dec 15, inc 23,
text[dec:inc+1]  maraca.
 break else
 s a maraca. 
dec 13, inc 23,
text[dec:inc+1]  a maraca.
 break else
 s , a maraca. 
dec 11, inc 23,
text[dec:inc+1] n, a maraca.
 break else
 s an, a maraca. 
dec 9, inc 23,
text[dec:inc+1] man, a maraca.
 break else
 s  man, a maraca. 
dec 7, inc 23,
text[dec:inc+1] a man, a maraca.
 break else
 s  a man, a maraca. 
dec 5, inc 23,
text[dec:inc+1] , a man, a maraca.
 break else
 s r, a man, a maraca. 
dec 3, inc 23,
text[dec:inc+1] ar, a man, a maraca.
 break else
 s car, a man, a maraca. 
dec 1, inc 23,
text[dec:inc+1]  car, a man, a maraca.
 break else
 s a car, a man, a maraca. 
Out[8]: ((13, 16), ' a ', ['', ' a ', 'c', ' ', 'aca', 'ara', 'r'])

Sometimes, it doesn't work at all:

有时，它根本不起作用：

    pal('madam')
    dec -1, inc 1,
    text[dec:inc+1] 
     s m 
    dec 1, inc 3,
    text[dec:inc+1] ada
     break 1st elif
     s m 
    dec 2, inc 4,
    text[dec:inc+1] dam
     break 1st elif
     s m 
    dec 3, inc 5,
    text[dec:inc+1] am
     break 1st elif
     s m 
    Out[5]: ((0, 1), 'm', ['m'])

Now considering madam is a very nice palindrome it should work and there are many cases which i haven't tested myself to find out what other legitimate palindromes it doesn't detect.

现在考虑到 madam 是一个非常好的回文，它应该可以工作，而且有很多情况我还没有测试过自己，以找出它没有检测到的其他合法回文。

Q1: Why is it sometimes not detecting?

Q1：为什么有时检测不到？

Q2: I would like to optimize my second code for that matter. Any inputs?

Q2：我想为此优化我的第二个代码。任何输入？

Q3: What better approach is there for a much much more efficient code than my First code which iterates many a times?

问题 3：对于比我的多次迭代的 First 代码更高效的代码，有什么更好的方法？

采纳答案by Blender

Your solution seems a bit complicated to me. Just look at all of the possible substrings and check them individually:

你的解决方案对我来说似乎有点复杂。只需查看所有可能的子字符串并单独检查它们：

def palindromes(text):
    text = text.lower()
    results = []

    for i in range(len(text)):
        for j in range(0, i):
            chunk = text[j:i + 1]

            if chunk == chunk[::-1]:
                results.append(chunk)

    return text.index(max(results, key=len)), results

text.index()will only find the first occurrence of the longest palindrome, so if you want the last, replace it with text.rindex().

text.index()只会找到最长回文的第一次出现，所以如果你想要最后一个，请将其替换为text.rindex().

回答by Magic Lui

I have to agree the solution may seem to complicated, i think the best solution, to find the largest palindrome in a subsequence, (considering characters in between for example in 'character' the largest palindrome should be carac) is:

我必须同意该解决方案可能看起来很复杂，我认为最好的解决方案是在子序列中找到最大的回文，（考虑中间的字符，例如在“字符”中，最大的回文应该是 carac）是：

def find_char_backwards(a, c):
for i in range(len(a) - 1, -1,-1):
    if a[i] == c:
        index=i
        return True, index

return False, 0

def longest_palindorme(a):
if len(a) < 2:
    return a
else:
    c=a[0]
    (exist_char,index) = find_char_backwards(a[1:],c)
    if exist_char:
        palindrome=[c] + longest_palindorme(a[1:index+1]) + [c]
    else:
        palindrome=[]
    rest_palidorme=longest_palindorme(a[1:])

if len(palindrome)>len(rest_palidorme):
    return palindrome
else:
    return rest_palidorme

Where a is an array, this solution uses recursion, and dynamic programming

其中 a 是数组，此解决方案使用递归和动态编程

回答by Bob

Use a nested loop:

使用嵌套循环：

for x in range(len(body)):
    for y in range(len(body)):
    ...

回答by Gaurav Padgilwar

a = "xabbaabba"  # Provide any string

count=[]
for j in range(len(a)):
    for i in range(j,len(a)):
        if a[j:i+1] == a[i:j-1:-1]:      
            count.append(i+1-j)

print("Maximum size of Palindrome within String is :", max(count))

回答by Abhishek Mishra

If you like the recursive solution, I have written a recursive version. It is also intuitive.

如果你喜欢递归解决方案，我已经写了一个递归版本。它也很直观。

def palindrome(s):
  if len(s) <= 1:
    return s
  elif s[0] != s[-1]:
    beginning_palindrome = palindrome(s[:-1])
    ending_palindrome = palindrome(s[1:])
    if len(beginning_palindrome) >= len(ending_palindrome):
      return beginning_palindrome
    else:
      return ending_palindrome
  else:
    middle_palindrome = palindrome(s[1:-1])
    if len(middle_palindrome) == len(s[1:-1]):
        return s[0] + middle_palindrome + s[-1]
    else:
        return middle_palindrome

回答by Acumenus

The following function returns the longest palindrome contained in a given string. It is just slightly different in that it uses itertoolsas suggested in this answer. There is value in abstracting away the combination generation. Its time complexity is evidently still cubic. It can trivially be adapted as needed to return the index and/or the list of palindromes.

以下函数返回给定字符串中包含的最长回文。它只是略有不同，因为它itertools按照本答案中的建议使用。抽象出组合生成是有价值的。它的时间复杂度显然仍然是三次方。它可以根据需要进行调整以返回索引和/或回文列表。

import itertools

def longest_palindrome(s):
    lp, lp_len = '', 0
    for start, stop in itertools.combinations(range(len(s)+1), 2):
        ss = s[start:stop]  # substring
        if (len(ss) > lp_len) and (ss == ss[::-1]):
            lp, lp_len = ss, len(ss)
    return lp

回答by senthil balaji

Here's a code you can use for finding the longest palindromic substring:

这是一个可用于查找最长回文子串的代码：

string = "sensmamstsihbalabhismadamsihbala"
string_shortener = ""
pres = 0
succ = 3
p_temp=0
s_temp=0
longest = ""
for i in range(len(string)-2):
    string_shortener = string[pres:succ]
    if(string_shortener==string_shortener[::-1]):
       p_temp = pres
       s_temp = succ
       for u in range(1000):
           p_temp-=1
           s_temp +=1
           string_shortener = string[p_temp:s_temp]
           if(string_shortener == string_shortener[::-1]):
                if len(string_shortener)>len(longest):
                    longest = string_shortener
            else:
                break
    pres+=1
    succ+=1
print(longest)

回答by Suraj Dubal

inputStr = "madammmdd"
outStr = ""
uniqStr = "".join(set(inputStr))
flag = False
for key in uniqStr:
   val = inputStr.count(key)
   if val % 2 !=0:
      if not flag:
         outStr = outStr[:len(outStr)/2]+key+outStr[len(outStr)/2:]
         flag=True
      val-=1
   outStr=key*(val/2)+outStr+key*(val/2)
print outStr

回答by Manish kumar

I have made function name as maxpalindrome(s) in this one string argument 's'. This function will return longest possible palindrome sub string and length of substring...

我在这个字符串参数 's' 中将函数名称设为 maxpalindrome(s)。此函数将返回最长可能的回文子串和子串的长度...

def maxpalindrome(s):
if len(s) == 1 or s == '':
    return str(len(s)) + "\n" + s
else:
    if s == s[::-1]:
        return str(len(s)) + "\n" + s
    else:
        for i in range(len(s)-1, 0, -1):
            for j in range(len(s)-i+1):
                temp = s[j:j+i]
                if temp == temp[::-1]:
                    return str(len(temp)) +"\n"+temp

回答by msilb

Here is another clean and simple approach taken from the excellent online course Design of Computer Programsby P. Norvig. It iterates over all characters in the string and attempts to "grow" the string to both left and right.

这是从P. Norvig的优秀在线课程Design of Computer Programs 中采用的另一种干净简单的方法。它遍历字符串中的所有字符，并尝试向左和向右“增长”字符串。

def longest_sub_palindrome_slice(text):
    "Return (i,j) such that text[i,j] is the longest palindrome in text"
    if text == '': return (0, 0)
    def length(slice): a,b = slice; return b-a
    candidates = [grow(text, start, end)
                 for start in range(len(text))
                 for end in (start, start + 1)]
    return max(candidates, key=length)

def grow(text, start, end):
    "Start with a 0- or 1- length palindrome; try to grow a bigger one"
    while (start > 0 and end < len(text)
           and text[start-1].upper() == text[end].upper()):
        start -= 1; end += 1
    return (start, end)