python 3 kmp 문자열 일치 하 는 방법

먼저,본인 의 풋내기 하 나 는 블 로 그 를 쓰 는 것 은 학습 과정 과 자신의 이해 와 소감 을 기록 하기 위해 서 입 니 다.어떤 곳 은 잘 쓰 지 못 할 수도 있 습 니 다.신 이 지적 해 주시 기 바 랍 니 다.
문 제 를 내던지다
텍스트 문자열 test 지정str(일치 하 는 문자열)와 패턴 문자열 patstr(텍스트 문자열 에서 일치 하 는 문자열 이 필요 합 니 다),텍스트 문자열 teststr 에서 패턴 문자열 찾기 patstr 처음 나타 난 자리,없 으 면 되 돌아 가기-1
폭력 적 방식
kmp 를 말 하기 전에 우 리 는 먼저'폭력 방식',즉 우리 의 가장 원시 적 인 방법 을 말한다.　


text_str = 'asdabcdace'
pat_str = 'abcdace'

def str_match(text_str,pat_str):
  for i in range(0,len(text_str)):
    j = 1
    while j < len(pat_str):
      if text_str[i:i+j] != pat_str[0:j]: # text_str i     ，       
        break  #    ，      ，i+1，          
      j += 1   #              ，  pat_str        
    if j == len(pat_str):
      return i
  return -1

print(str_match(text_str,pat_str))

폭력 해법 이 라 고 부 르 는 이 유 는 매 칭 에 실패 할 때마다 패턴 문자열 을 뒤로 이동 하고 처음부터 매 칭 하 며 계속 순환 하기 때문이다.시간 복잡 도가 높 습 니 다.kmp 즉,이 곳 을 최적화 하 는 것 입 니 다.매번 일치 에 실패 하고 다음 이동 거리 next 값 입 니 다.

KMP
만약 내 가 너 에 게 kmp 알고리즘 을 완전히 이해 하 게 한다 면 그리 쉽 지 않 을 것 이다.나 는 그것 의 한 걸음 한 걸음 을 대충 실현 할 수 밖 에 없다.딱 한 가지 포인트 라 고 생각 합 니 다.
어떻게 패턴 문자열 의 모든 문자 에 대응 하 는 next 값 을 구 합 니까?
실패 한 길이 와 일치 하 는 문자 가 다 를 수 있 기 때문에 이동 할 때마다 거리 가 다 를 수 있 습 니 다.그러면 우 리 는 모든 문자 에 대응 하 는 next 값 을 어떻게 구 하 는 지 다른 개념 을 이 끌 어 냈 습 니 다.
최대 접두사 와 최대 접두사
　　　　

최대 접두사=최대 접두사,길이 k 로 가정 하면 i 번 째 문자,대응 하 는 next 값 은 k+1 입 니 다.한 번 순환 하면 모든 문자 의 next 값 을 구 할 수 있 습 니 다.
코드 구현


#     next 
text_str = 'asdabcdace'
pat_str = 'abcdace'

#       next 
def str_next(s):
  #         1
  next = [1,1]
  for x in range(2,len(s)):
    next.append(str_max_prx(s,x,next[x-1]-1) + 1)
  return next
#   s   ，        ，         
def str_max_prx(s,x,last_value):
  next = 0
  for i in range(last_value,x):
    if s[0:i] == s[x-i:x]:
      next = i
  return next
def str_match(s,m):
  next = str_next(s)
  i=0
  s_len = len(s)
  m_len = len(m)
  while i <= m_len:
    flag = True   #   ，          
    index = 1
    while index <= s_len:
      if m[i:i + index] != s[0:index]:
        i = i + next[index]
        flag = False
        break
      else:
        index += 1
    if flag:
      break
  if i >= m_len:
    i = -1
  return i
res = str_match(pat_str,text_str)
print(res)

코드 가 이 렇 습 니 다.많은 것 을 스스로 이해 해 야 할 수도 있 습 니 다.나 는 나중에 찾기 편 하도록 필 기 를 해서 너 에 게 도움 이 되 기 를 바란다.많은 응원 부 탁 드 리 겠 습 니 다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Jupyter 공식 DockerHub에 대한 메모

에 기재되어 있다. base-notebook minimal-notebook scipy-notebook tensorflow-notebook datascience-notebook pyspark-notebook all-s...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

python 3 kmp 문자열 일치 하 는 방법

좋은 웹페이지 즐겨찾기