해당 글은 Do it! Python으로 배우는 자료구조와 알고리즘을 기반으로 작성했습니다.
문자열 검색
- 어떤 문자열 안에 다른 문자열(패턴)이 포함되어 있는지 검사
- 포함되어 있다면 어디에 위치하는지 찾아내는 것
브루트 포스법(단순법, 완전 탐색)
- 완전 탐색
- 선형 검색을 단순히 확장한 알고리즘
- 이미 검사한 위치를 기억하지 못 한다. ⇒ "일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검사 수행"
코드
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
멤버십 연산자와 표준 라이브러리를 사용한 문자열 검색
- 멤버십 연산자로 구현**, index를 알 수 없음**
- in
- not in
- str class
- find(sub[])
- index(sub[])
- rfind(sub[]): 가장 큰(우측) 인덱스
- rindex(sub[])
- with계열 함수
- startswith
- endswith
KMP법
- 건너뛰기표를 통해 브루트 포스법이 가지는 단점 해결
- 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴의 이동이 되도록 크게 하는 알고리즘
보이어 무어법
- 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사 수행
- 일치하지 않는 문자를 발견시 건너뛰기표를 바탕으로 패턴 이동하는 값 결정
건너뛰기표
- A ~ Z까지
- 패턴에 포함되지 않는 문자를 만난 경우
- 패턴 이동량 = n
- 포함되지 않으면 패턴 문자열의 길이(n)만큼 이동
- 패턴에 포함되는 문자를 만난 경우
- 같은 문자가 패턴 안에서 중복할 경우, ⇒ 패턴 이동량 = n - k - 1
- k: 마지막에 나오는 위치의 인덱스
같은 문자가 패턴 안에서 중복하지 않을 경우, ⇒ 패턴의 맨 끝 문자의 이동량 = n ?!⇒ 0?
- 같은 문자가 패턴 안에서 중복할 경우, ⇒ 패턴 이동량 = n - k - 1
# 건너뛰기표에서 사용하는 원소 개수: 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 = 패턴의 길이
- 브루트 포스법: O(n)
- KMP법: O(n)
- 보이어 무어법: O(n/m), 최악의 경우 O(n)
⇒ 표준 라이브러리 사용하는 것 추천!