Python 문자열 일치 알고리즘 코드 예제 구현

질문
Python 에서 긴 문자열 에서 하위 문자열 이 존재 하 는 지 찾 으 려 면 두 가지 방법 을 사용 하 십시오.하 나 는 str 의 find()함수 이 고 find()함 수 는 하위 문자열 이 일치 하 는 시작 위치 만 되 돌려 줍 니 다.없 으 면-1 로 되 돌려 줍 니 다.둘 째 는 re 모듈 의 findall 함수 로 일치 하 는 모든 하위 문자열 을 되 돌려 줍 니 다.
그러나 findall 함 수 를 사용 할 때 문자열 에 존재 하 는 특수 문 자 를 주의해 야 합 니 다.
만력 법 문자열 일치:
패턴 을 텍스트 의 앞 m(패턴 길이)문 자 를 맞 춘 다음 왼쪽 에서 오른쪽으로 모든 일치 하거나 일치 하지 않 는 문 자 를 만 날 때 까지 일치 합 니 다.다음 상황 에서 모드 를 오른쪽으로 이동 합 니 다.
코드 는 다음 과 같 습 니 다:

def string_match(string, sub_str): 
 #          
 for i in range(len(string)-len(sub_str)+1): 
  index = i  # index            
  for j in range(len(sub_str)): 
   if string[index] == sub_str[j]: 
    index += 1 
   else: 
    break 
   if index-i == len(sub_str): 
    return i 
 return -1 

if __name__ == "__main__": 
 print(string_match("adbcbdc", "dc")) 

최 악의 경우 이 알고리즘 은Θ(nm),사실상 이 알고리즘 의 평균 효율 은 최 악의 효율 보다 훨씬 좋다.사실 무 작위 텍스트 를 찾 을 때 선형 효율 에 속한다.Θ(n)。
Horspool 알고리즘:
Horsepool 알고리즘 은 Boyer-Moore 알고리즘 의 간략화 버 전 으로 공간 이 시간 을 바 꾸 는 전형 적 인 예 이기 도 합 니 다.알고리즘 은 패턴 P 와 텍스트 T 의 시작 문 자 를 정렬 하고 패턴 의 마지막 문자 부터 비교 합 니 다.비교 에 실패 하면 패턴 을 뒤로 이동 합 니 다.매번 시도 하 는 과정 에서 비 교 는 오른쪽 에서 왼쪽으로 한다.
만력 알고리즘 에서 패턴 의 모든 이동 은 하나의 문자 이 고 Horspool 알고리즘 의 핵심 사상 은 공간 을 이용 하여 시간 을 바 꾸 고 패턴 이 창 과 일치 하 는 이동 폭 을 향상 시 키 는 것 입 니 다.만력 알고리즘 과 달리 그 패턴 의 매 칭 은 오른쪽 에서 왼쪽으로 이 며,매번 이동 하 는 거 리 를 미리 계산 하여 표 에 병존 한다.
코드 는 다음 과 같 습 니 다:

__author__ = 'Wang' 
from collections import defaultdict 
def shift_table(pattern): 
 #    Horspool        
 #        c，     m 
 #     c        m-1    ，       m 
 #             c             
 table = defaultdict(lambda: len(pattern)) 
 for index in range(0, len(pattern)-1): 
  table[pattern[index]] = len(pattern) - 1 - index 
 return table 
def horspool_match(pattern, text): 
 #    horspool         
 #     ，     text      ；     -1 
 table = shift_table(pattern) 
 index = len(pattern) - 1 
 while index <= len(text) - 1: 
  print("start matching at", index) 
  match_count = 0 
  while match_count < len(pattern) and pattern[len(pattern)-1-match_count] == text[index-match_count]: 
   match_count += 1 
  if match_count == len(pattern): 
   return index-match_count+1 
  else: 
   index += table[text[index]] 
 return -1 

if __name__ == "__main__": 
 print(horspool_match("barber", "jim_saw_me_in_a_barbershopp")) 

분명히 Horspool 알고리즘 의 최 악의 효율 은Θ(nm)。무 작위 텍스트 를 찾 을 때 선형 효율 에 속 합 니 다.Θ(n)。효율 유형 은 같 지만 평균 적 으로 Horspool 알고리즘 은 만력 알고리즘 보다 훨씬 빠르다.
총결산
이상 은 Python 이 문자열 일치 알고리즘 코드 예제 에 관 한 모든 내용 입 니 다.도움 이 되 기 를 바 랍 니 다.관심 이 있 는 친 구 는 본 사 이 트 를 계속 참고 할 수 있 습 니 다.
Python 스케줄 링 알고리즘 코드 상세 설명 실현
Python 알고리즘 그림 옮 겨 다 니 기
Python 프로 그래 밍 개미 떼 알고리즘 상세 해석 실현
부족 한 점 이 있 으 면 댓 글로 지적 해 주세요.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!