python 은 최 장 회 문 하위 문자열 에 대한 동적 계획 알고리즘 을 실현 합 니 다.

Python 을 바탕 으로 최 장 회 문 하위 문자열 에 대한 동적 계획 알고리즘 을 실현 합 니 다.구체 적 인 내용 은 다음 과 같 습 니 다.
1.제목
문자열 s 를 지정 하여 s 에서 가장 긴 답장 문자열 을 찾 습 니 다.너 는 s 의 최대 길이 가 1000 이 라 고 가정 할 수 있다.
예시 1:
입력:"babad"
출력:"bab"
주의:"aba"도 하나의 유효한 답안 이다.
예시 2:
입력:"cbbd"
출력:"bb"
2.구 해
폭력 에 대한 해답 은 여기 서 더 이상 오 술 하지 않 고 동적 기획 알고리즘 을 어떻게 활용 하여 해답 을 구 하 는 지 에 중심 을 두 었 다.
동적 계획 의 의미 와 용법 에 대해 참고 하 시기 바 랍 니 다링크이 글 은 만화 의 형식 을 통 해 동적 계획 알고리즘 에 대해 상세 하고 재 미 있 는 소 개 를 했 습 니 다.볼만 하 다.
2.1 알고리즘 1
일반적인 동적 계획 알고리즘,즉 표를 이용 하여 모든 답장 하위 문자열 을 저장 할 수 있 습 니 다.
동적 계획 의 세 가지 요 소 를 바탕 으로 문 제 를 분석 하면 다음 과 같은 상태 전환 방정식 을 확정 할 수 있다.

그 중에서 f(i,j)는 s[i:j]하위 문자열 이 답장 문자열 인지 아 닌 지 를 나타 낸다.j-i<=1 일 때 s[i]=s[j]는 s[i:j]를 답장 문자열 로 하고 f(i,j)=true 를 표시 합 니 다.그렇지 않 으 면 f(i,j)=false 를 표시 합 니 다.j-i>1 시 s[i],s[j]가 같은 지,f(i+1,j-1)가 true 인지,즉 s[i+1:j-1]가 리 턴 문자열 인지,진실 이 라면 f(i,j)=true 인지 판단 합 니 다.
그래서 n*n 의 2 차원 행렬 이 f(i,j)의 값 을 저장 하 는 데 사용 되 어야 합 니 다.그 중에서 j in range(0,k),i in range(0,j+1)가 필요 합 니 다.j+1 은 i 가 j 와 같 을 수 있 기 때 문 입 니 다.
python 3 코드 는 다음 과 같 습 니 다:

 k = len(s) #          
 matrix = [[0 for i in range(k)] for i in range(k)] #    n*n    
 logestSubStr = "" #          
 logestLen = 0 #           
 
  for j in range(0, k): 
   for i in range(0, j+1): 
    if j - i <= 1: 
     if s[i] == s[j]: 
      matrix[i][j] = 1   #   f(i,j)  true 
      if logestLen < j - i + 1: #  s[i:j]                   
       logestSubStr = s[i:j+1] #            
       logestLen = j - i + 1 #             
    else: 
     if s[i] == s[j] and matrix[i+1][j-1]: #    
      matrix[i][j] = 1 
      if logestLen < j - i + 1: 
       logestSubStr = s[i:j+1] 
       logestLen = j - i + 1 
  return logestSubStr 

 현재 알고리즘 을 사용 하면 시간 복잡 도 는 O(n*n)이 고 공간 복잡 도 는 O(n*n)이 며 알고리즘 은 평균 5~7s 정도 걸 립 니 다.
다음은 공간 복잡 도가 O(n)인 알고리즘 을 소개 한다.
2.2 알고리즘 2
알고리즘 2 는 알고리즘 1 을 개량 한 것 으로 알고리즘 1 의 집행 절 차 를 관찰 하면 다음 과 같다.

j>1 시 f(i,j)가 답문 하위 문자열 인지 아 닌 지 를 판단 하 는 작업 은 j-1 시의 작업 과 만 관련 이 있 습 니 다.즉,f(i,j)=g(f(i,j-1)입 니 다.그 중에서 j>1,i in range(0,j+1)이기 때문에 다음은 g()함수 가 됩 니 다.   
nlist 로 j 상황 에서 모든 하위 문자열 이 답장 하위 문자열 의 표지 인지 저장 합 니 다.
j-1 상황 에서 모든 하위 문자열 이 답장 하위 문자열 의 표지 인지 olist 로 저장 합 니 다.
그렇다면 올 리 스 트 와 nlist 의 관 계 는 무엇 일 까?

위의 그림 에서 알 수 있 듯 이 nlist[i]=g(olist[i+1])
새로운 알고리즘 은 다음 과 같다.

k = len(s) 
 olist = [0] * k #      n   ，     
nList = [0] * k #    
logestSubStr = "" 
 logestLen = 0 
 
  for j in range(0, k): 
   for i in range(0, j + 1): 
    if j - i <= 1: 
     if s[i] == s[j]: 
      nList[i] = 1 #   j  ，  i          
      len_t = j - i + 1 
      if logestLen < len_t: #      
       logestSubStr = s[i:j + 1] 
       logestLen = len_t 
    else: 
     if s[i] == s[j] and olist[i+1]: #  j-i>1 ，  s[i]    s[j]，    j-1 ， i+1           
      nList[i] = 1 #   j  ，  i          
      len_t = j - i + 1 
      if logestLen < len_t: 
       logestSubStr = s[i:j + 1] 
       logestLen = len_t 
   olist = nList  #        
   nList = [0] * k #        
  return logestSubStr 

 이렇게 새로운 알고리즘 의 공간 복잡 도 는 O(2n),즉 O(n)이다.알고리즘 은 평균 3s 정도 걸 리 고 이 알고리즘 은 동적 계획 의 원리 에 더욱 부합된다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.