Python 은 주어진 문자열 에 대해 최 장 반복 되 지 않 는 하위 문자열 을 찾 는 방법 을 실현 합 니 다.

이 사례 는 Python 이 주어진 문자열 에 대해 최 장 반복 되 지 않 는 하위 문자열 을 찾 는 방법 을 보 여 줍 니 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
질문:
문자열 을 지정 하여 가장 긴 중복 하위 시퀀스 를 찾 습 니 다.문자열 이 하나의 문자 로 구성 되 어 있다 면"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
생각:
여기 서 생각 나 는 게 두 가지 가 있어 요.
(1)처음부터 문자열 을 옮 겨 다 니 며 표지 위 치 를 설정 합 니 다.뒤로 가 는 과정 에서 이전 표지 위치 와 겹 치 는 것 을 발견 하면 새로 나타 난 하위 문자열 이 앞 문자열 이나 앞 문자열 의 하위 문자열 과 같 는 지 다시 확인 합 니 다.마찬가지 로 이 하위 문자열 을 기록 하고 1 을 추가 합 니 다.
(2)미끄럼 창 슬라이스 체 제 를 이용 하여 모든 슬라이스 를 생 성 한 다음 에 통계 와 처 리 를 하 는데 주로 두 번 의 정렬 기능 을 이용 했다.
본 고 는 두 번 째 방법 을 채택 하 였 는데 다음은 구체 적 인 실현 이다.

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:    
  :       ,        
'''
from collections import Counter
def slice_window(one_str,w=1):
  '''''
      
  '''
  res_list=[]
  for i in range(0,len(one_str)-w+1):
    res_list.append(one_str[i:i+w])
  return res_list
def main_func(one_str):
  '''''
     
  '''
  all_sub=[]
  for i in range(1,len(one_str)):
    all_sub+=slice_window(one_str,i)
  res_dict={}
  #print Counter(all_sub)
  threshold=Counter(all_sub).most_common(1)[0][1]
  slice_w=Counter(all_sub).most_common(1)[0][0]
  for one in all_sub:
    if one in res_dict:
      res_dict[one]+=1
    else:
      res_dict[one]=1
  sorted_list=sorted(res_dict.items(), key=lambda e:e[1], reverse=True)
  tmp_list=[one for one in sorted_list if one[1]>=threshold]
  tmp_list.sort(lambda x,y:cmp(len(x[0]),len(y[0])),reverse=True)
  #print tmp_list
  print tmp_list[0][0]
if __name__ == '__main__':
  print "      :"
  one_str='abcabcd'
  two_str='abcabcabd'
  three_str='bbbbbbb'
  main_func(one_str)
  main_func(two_str)
  main_func(three_str)

결 과 는 다음 과 같다.

더 많은 파 이 썬 관련 내용 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.

좋은 웹페이지 즐겨찾기