python longest palindrome string algorithm

This article mainly introduces the practice of Python's longest palindrome string algorithm in detail. It has certain reference value. Interested friends can refer to it

Given a string, the requirements Find the longest substring in this string that conforms to the palindrome property. The so-called palindrome refers to strings such as "aba", "ababa", and "abba". Of course, a single character and two adjacent identical characters also satisfy the palindrome property.

When seeing this problem, the first solution that comes to mind is naturally violent enumeration. By enumerating the starting points of all strings in a string, one by one determines the substrings that satisfy palindromic properties, records the length and updates the longest length. Obviously, the time complexity of this algorithm is very high, and can reach O(N*N) in the worst case. Therefore, an optimized solution is proposed here. By enumerating the center of the string substrings instead of the starting point, spreading to both sides at the same time, the palindromic nature of the substrings is still judged one by one. This optimization algorithm is much more efficient than the previous algorithm in the worst case (that is, a string with only one character).

From the above optimization plan, we know that enumerating the center is more efficient than enumerating the points, but this is not the optimal algorithm. Since the algorithm for enumerating the center affects the characters on both sides of the center at the same time, we can judge the palindrome of the substring by enumerating the characters to the left of the center as the center and judging the palindrome of the substring that enumerates the characters to the right of the center as the center. , this is the manager algorithm.

The manacher algorithm idea is very clever. First traverse the string, assuming i is the enumeration center, then j (jb0fbc1b6eb82025851cdb97755391e8c=f[i']

2 . The influence range of the character i' that is symmetrical about j is not completely included in the influence range of j. At this time, the influence range of the right side of i is greater than or equal to [j-f[j]/2,i'], that is, i f[i]/ 2>=i'-j f[j]/2

Due to symmetry, we can get i i" = 2*j. Therefore, in the first case, f[i]>=f[2*j-i ]; In the second case, f[i]>=f[j] 2*j-2*i.

Based on the above 1,2, we can get f[i]>=min( f[2*j-i],f[j] 2*j-2*i). Since there are untraversed characters on the right side of i, on this basis, continue to expand to both sides until the longest palindrome substring is found.

If i is still behind j f[j]/2, it means that i is not affected by the previous characters and can only expand to both sides one by one.

This algorithm only needs to traverse the characters once String, the number of expansions is also limited, so the time complexity can reach O(N).

The following is the program of Pthon3. In order to test the efficiency of the algorithm, the original violent enumeration algorithm is still provided as the worst algorithm Reference.

python code:

#求最长回文串类 
class LPS:           
  #初始化，需要提供一个字符串  
  def __init__(self,string): 
    self.string = string 
    self.lens = len(self.string) 
   
  #暴力枚举：作为算法效率参照 
  def brute_force(self): 
    maxcount = 0 
    for j in range(self.lens):            
      for k in range(j,self.lens): 
        count = 0 
        l,m = j,k 
        while m>=l: 
          if self.string[l]==self.string[m]: 
            l,m = l+1,m-1 
          else: 
            break 
        if m<l: 
          count = k-j+1 
        if count>maxcount : 
          maxcount = count 
    return maxcount 
   
  #优化版：枚举子串中心 
  def brute_force_opti(self): 
    maxcount = 0 
    if self.lens == 1:               #只有一个字符直接返回1 
      return 1 
    for j in range(self.lens-1):          #枚举中心 
      count,u = 1,j  
      #对于奇数子串，直接扩展 
      for k in range(1,j+1):           #两边扩展 
        l,m = u+k,j-k 
        if (m>=0)&(l<self.lens): 
          if(self.string[l]==self.string[m]): 
            count += 2 
          else: 
            break 
      if count>maxcount :             #更新回文子串最长长度 
        maxcount = count 
      if self.string[j]==self.string[j+1]:    #处理偶数子串，将两个相邻相同元素作为整体 
        u,count= j+1,2 
      for k in range(1,j+1):           #两边扩展 
        l,m = u+k,j-k 
        if (m>=0)&(l<self.lens): 
          if(self.string[l]==self.string[m]): 
            count += 2 
          else: 
            break 
      if count>maxcount :             #更新回文子串最长长度 
        maxcount = count 
    return maxcount 
     
  #manacher算法 
  def manacher(self): 
    s = &#39;#&#39;+&#39;#&#39;.join(self.string)+&#39;#&#39;        #字符串处理，用特殊字符隔离字符串，方便处理偶数子串 
    lens = len(s) 
    f = []                     #辅助列表：f[i]表示i作中心的最长回文子串的长度 
    maxj = 0                    #记录对i右边影响最大的字符位置j 
    maxl = 0                    #记录j影响范围的右边界 
    maxd = 0                    #记录最长的回文子串长度 
    for i in range(lens):              #遍历字符串 
      if maxl>i:                  
        count = min(maxl-i,int(f[2*maxj-i]/2)+1)#这里为了方便后续计算使用count，其表示当前字符到其影响范围的右边界的距离 
      else :                    
        count = 1 
      while i-count>=0 and i+count<lens and s[i-count]==s[i+count]:#两边扩展 
        count +=1 
      if(i-1+count)>maxl:             #更新影响范围最大的字符j及其右边界 
          maxl,maxj = i-1+count,i                             
      f.append(count*2-1) 
      maxd = max(maxd,f[i])            #更新回文子串最长长度 
    return int((maxd+1)/2)-1            #去除特殊字符

Through the above program, use the string as a pure 'a' of length 1000 String as a sample, tested:

Violent enumeration: 49.719844s

Central enumeration: 0.334019s

manacher: 0.008000s

It can be seen that when the length is 1000, the time-consuming of violent enumeration is unbearable. In comparison, the efficiency of central enumeration has been greatly improved, and the optimal manager time-consuming is Shorter.

Related recommendations:

Python implementation to determine whether a string is a legal IP address

Python for a given string Method to determine whether all subsequences are palindrome sequences

##

The above is the detailed content of python longest palindrome string algorithm. For more information, please follow other related articles on the PHP Chinese website!