728x90 KMP1 [Algorithm] 패턴 매칭 알고리즘 - KMP, 보이어-무어 고지식한 패턴 검색 알고리즘 (Brute Force) 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교 시간 복잡도 O(MN) -> 최악의 경우 텍스트의 모든 위치 패턴 비교해야하므로 p = 'is' # 찾을 패턴 (target) M = len(p) t = 'This is a book~!' # 전체 텍스트 N = len(t) def BruteForce(p, t): i = 0 # t의 인덱스 j = 0 # p의 인덱스 while j < M and i < N: if t[i] != p[j]: i -= j j = -1 i += 1 j += 1 if j == M: return i - M # 검색성공 else: return -1 # 검색실패 카프-라빈 알고리즘 고지식한 패턴 검색 알.. 2021. 8. 22. 이전 1 다음 728x90