이 글은 주로 Python의 가장 긴 회문 문자열 알고리즘의 실행을 자세히 소개합니다. 여기에는 특정 참조 값이 있습니다. 관심 있는 친구는 이를 참조할 수 있습니다.
문자열이 주어지면 이 문자열에서 찾아야 합니다. 회문 속성. 소위 회문은 "aba", "ababa", "abba"와 같은 문자열을 나타냅니다. 물론 단일 문자와 인접한 두 개의 동일한 문자도 회문 속성을 충족합니다.
이 문제를 볼 때 가장 먼저 떠오르는 해결책은 문자열의 모든 문자열의 시작점을 열거함으로써 회문을 만족하는 부분 문자열을 하나씩 결정하고 길이를 기록하고 가장 긴 것을 업데이트하는 것입니다. 길이. 분명히 이 알고리즘의 시간 복잡도는 매우 높으며 최악의 경우 O(N*N)에 도달할 수 있습니다. 따라서 여기서는 시작점 대신 문자열 부분 문자열의 중심을 열거하고 동시에 양쪽으로 확산시켜 부분 문자열의 회문 특성을 하나씩 판단하는 최적화된 솔루션을 제안합니다. 이 최적화 알고리즘은 최악의 경우(즉, 문자가 하나만 있는 문자열)에서 이전 알고리즘보다 훨씬 더 효율적입니다.
위의 최적화 계획을 통해 점을 열거하는 것보다 중심을 열거하는 것이 더 효율적이라는 것을 알 수 있지만 이는 최적의 알고리즘은 아닙니다. 중심을 열거하는 알고리즘은 중심을 기준으로 양쪽 문자에 동시에 영향을 주기 때문에 중심에서 왼쪽에 있는 문자를 중심으로 열거하고, 중심 문자열의 회문을 판단하면 부분 문자열의 회문을 판단할 수 있다. 중앙의 오른쪽에 있는 문자를 중앙으로 열거하는 것이 관리자 알고리즘입니다.
manacher 알고리즘의 아이디어는 매우 영리합니다. 먼저 i가 열거 중심이고 j(j 1 i는 문자 i'입니다. j에 대해 대칭이다 영향의 범위는 j의 범위에 완전히 포함되며, 그러면 회문으로 인해 i의 영향 범위는 i'의 영향 범위보다 크거나 같습니다. 즉, f[i]> ;=f[i'] 2. i에 대한 대칭 문자 i'의 영향 범위는 j의 영향 범위에 완전히 포함되지 않습니다. 이때 i의 오른쪽의 영향 범위는 보다 큽니다. 또는 [j-f[j]/2,i']와 같습니다. 즉, i+f[i]/2> =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. 알고리즘의 효율성을 테스트하기 위해 원래의 무차별 열거 알고리즘은 여전히 최악의 알고리즘에 대한 참조로 제공됩니다. 위 프로그램을 통해 순수 'a' 문자열을 사용합니다. 예를 들어 길이 1000, 테스트됨: 중앙 열거: 0.334019s manacher: 0.008000s 길이가 1000일 때 폭력적인 이에 비해 열거형의 효율성이 크게 향상되었으며, 최적의 관리자 시간 소모가 더 짧아졌습니다. 관련 권장 사항: 위 내용은 파이썬에서 가장 긴 회문 문자열 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!#求最长回文串类
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 = '#'+'#'.join(self.string)+'#' #字符串处理，用特殊字符隔离字符串，方便处理偶数子串
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 #去除特殊字符
폭력적인 열거: 49.719844s
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
