집 >백엔드 개발 >파이썬 튜토리얼 >파이썬에서 가장 긴 회문 문자열 알고리즘

파이썬에서 가장 긴 회문 문자열 알고리즘

不言원래의: 2018-06-04 16:26:252067검색

이 글은 주로 Python의 가장 긴 회문 문자열 알고리즘의 실행을 자세히 소개합니다. 여기에는 특정 참조 값이 있습니다. 관심 있는 친구는 이를 참조할 수 있습니다.

문자열이 주어지면 이 문자열에서 찾아야 합니다. 회문 속성. 소위 회문은 "aba", "ababa", "abba"와 같은 문자열을 나타냅니다. 물론 단일 문자와 인접한 두 개의 동일한 문자도 회문 속성을 충족합니다.

이 문제를 볼 때 가장 먼저 떠오르는 해결책은 문자열의 모든 문자열의 시작점을 열거함으로써 회문을 만족하는 부분 문자열을 하나씩 결정하고 길이를 기록하고 가장 긴 것을 업데이트하는 것입니다. 길이. 분명히 이 알고리즘의 시간 복잡도는 매우 높으며 최악의 경우 O(N*N)에 도달할 수 있습니다. 따라서 여기서는 시작점 대신 문자열 부분 문자열의 중심을 열거하고 동시에 양쪽으로 확산시켜 부분 문자열의 회문 특성을 하나씩 판단하는 최적화된 솔루션을 제안합니다. 이 최적화 알고리즘은 최악의 경우(즉, 문자가 하나만 있는 문자열)에서 이전 알고리즘보다 훨씬 더 효율적입니다.

위의 최적화 계획을 통해 점을 열거하는 것보다 중심을 열거하는 것이 더 효율적이라는 것을 알 수 있지만 이는 최적의 알고리즘은 아닙니다. 중심을 열거하는 알고리즘은 중심을 기준으로 양쪽 문자에 동시에 영향을 주기 때문에 중심에서 왼쪽에 있는 문자를 중심으로 열거하고, 중심 문자열의 회문을 판단하면 부분 문자열의 회문을 판단할 수 있다. 중앙의 오른쪽에 있는 문자를 중앙으로 열거하는 것이 관리자 알고리즘입니다.

manacher 알고리즘의 아이디어는 매우 영리합니다. 먼저 i가 열거 중심이고 j(jb438a694675025a6da3b57b696ab362e =i'-j+f[j]/2

대칭으로 인해 i+를 얻을 수 있습니다. i" = 2*j. 따라서 첫 번째 경우 f[i]>=f[2*j-i]; 두 번째 경우 f[i]>=f[j]+2*j-2 *i.

위의 1,2를 토대로 f[i]>=min(f[2*j-i ],f[j]+2*j-2*i)를 얻을 수 있습니다. i 오른쪽에 있는 문자는 가장 긴 회문 하위 문자열을 찾을 때까지 양쪽으로 계속 확장됩니다.

i가 여전히 존재하는 경우 j+f[j]/2 이후에는 i가 이전 문자의 영향을 받지 않으며

이 알고리즘은 문자열을 한 번만 탐색하면 되며, 확장 횟수도 O(N)에 도달할 수 있습니다.

다음은 프로그램입니다. Pthon3. 알고리즘의 효율성을 테스트하기 위해 원래의 무차별 열거 알고리즘은 여전히 최악의 알고리즘에 대한 참조로 제공됩니다.

#求最长回文串类 
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            #去除特殊字符

위 프로그램을 통해 순수 'a' 문자열을 사용합니다. 예를 들어 길이 1000, 테스트됨:

폭력적인 열거: 49.719844s

중앙 열거: 0.334019s

manacher: 0.008000s

길이가 1000일 때 폭력적인 이에 비해 열거형의 효율성이 크게 향상되었으며, 최적의 관리자 시간 소모가 더 짧아졌습니다.

파이썬에서 가장 긴 회문 문자열 알고리즘

관련 기사