[Do it! Python] 문자열 검색

해당 글은 Do it! Python으로 배우는 자료구조와 알고리즘을 기반으로 작성했습니다. 

문자열 검색

1. 어떤 문자열 안에 다른 문자열(패턴)이 포함되어 있는지 검사
2. 포함되어 있다면 어디에 위치하는지 찾아내는 것

브루트 포스법(단순법, 완전 탐색)

• 완전 탐색
• 선형 검색을 단순히 확장한 알고리즘
• 이미 검사한 위치를 기억하지 못 한다. ⇒ "일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검사 수행"

코드

def bf_match(txt, pat):
	pt = 0 # txt를 스캔하는 커서 
	pp = 0 # 패턴을 저장하는 pat을 스캔하는 커서 

	while pt != len(txt) and pp != len(pat):
		if txt[pt] == pat[pp]:
			pt += 1
			pp += 1

		else:
			pt = pt - pp + 1
			pp = 0

	return pt - pp if pp == len(pat) else -1 # 패턴pat 여러번 포함되면 맨 앞만,검색 실패 -1

멤버십 연산자와 표준 라이브러리를 사용한 문자열 검색

1. 멤버십 연산자로 구현**, index를 알 수 없음**
   • in
   • not in
2. str class
   • find(sub[])
   • index(sub[])
   • rfind(sub[]): 가장 큰(우측) 인덱스
   • rindex(sub[])
3. with계열 함수
   • startswith
   • endswith

KMP법

• 건너뛰기표를 통해 브루트 포스법이 가지는 단점 해결
• 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴의 이동이 되도록 크게 하는 알고리즘

보이어 무어법

• 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사 수행
• 일치하지 않는 문자를 발견시 건너뛰기표를 바탕으로 패턴 이동하는 값 결정

건너뛰기표

1. A ~ Z까지
2. 패턴에 포함되지 않는 문자를 만난 경우
   • 패턴 이동량 = n
   • 포함되지 않으면 패턴 문자열의 길이(n)만큼 이동
3. 패턴에 포함되는 문자를 만난 경우
   • 같은 문자가 패턴 안에서 중복할 경우, ⇒ 패턴 이동량 = n - k - 1
     • k: 마지막에 나오는 위치의 인덱스
   • 같은 문자가 패턴 안에서 중복하지 않을 경우, ⇒ 패턴의 맨 끝 문자의 이동량 = n ?! ⇒ 0?

# 건너뛰기표에서 사용하는 원소 개수: 256개
def bm_match(txt, pat):
	skip = [None] * 256

	# 건너뛰기표 만들기
	for pt in range(256):
		skip[pt] = len(pat)
	for pt in range(len(pat)):
		skip[ord(pat[pt])] = len(pat) - pt - 1

	# 검색하기 
	while pt < len(txt):
		pp = len(pat) -1 
		while txt[pt] == pat[pp]:
			if pp == 0:
				return pt
			pt -= 1
			pp -= 1
	pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp \
				esle len(pat) - pp
	
	return -1

문자열 검색 알고리즘의 시간 복잡도

• n = 텍스트 길이, m = 패턴의 길이

1. 브루트 포스법: O(n)
2. KMP법: O(n)
3. 보이어 무어법: O(n/m), 최악의 경우 O(n)

⇒ 표준 라이브러리 사용하는 것 추천!