브루트 포스법
전수 공격법으로, 문자열에 맞는 모든 경우의 수를 다 체크하는 방식입니다. 전체 문자열과 찾는 대상 문자열, 두 문자열의 검색 위치를 잡아주는 pt, pp 변수를 선언하고 확인해나갑니다.
def bf_match(txt: str, pat: str) -> int:
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
① ABABCDEF 에서 ABC 검색
② pt = 2, pp = 2 까지 증가
③ txt[pt] != pat[pp] 이므로 pt = 1, pp = 0으로 초기화. 즉, txt[1]부터 검색 진행
멤버십 연산자와 표준 라이브러리를 사용한 문자열 검색
1. 멤버십 연산자로 구현하기
in, not in
# ptn in txt
# ptn not in txt
in과 not in을 사용하면 어떤 문자열이 다른 문자열 안에 포함되어 있는지 검색할 수 있습니다.
2. find, index 계열 함수로 구현하기
str 클래스형에 소속된 다음 함수를 사용하여 문자열을 검색하고, 검색한 문자열의 위치를 반환합니다.
find(), rfind(), index(), rindex()
KMP법
앞선 포스트에서 브루트 포스법은 일치하지 않는 문자를 만나면 이전 단계에서 검사했던 결과를 버리고 패턴의 첫 문자부터 다시 검사를 수행하는 방식이었습니다. KMP법은 검사했던 결과를 버리지 않고 효율적으로 활용합니다.
KMP법은 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여, 패턴의 이동을 되도록이면 크게 하는 알고리즘입니다.
① ZABCABXACCADEF에서 ABCABD 찾기
② 브루트 포스법은 ABCABX의 X와 ABCABD의 D가 같지 않으므로, BCABXA와 ABCABD를 비교합니다. KMP는 X 앞의 AB와 찾는 문자열 맨 앞의 AB에 주목합니다. 즉, index = 1번째 검사를 한 결과를 주목하고, 다음 검사 시에는 X 이후 부분이 CABD와 일치하는지 검사합니다.
③ 이때 바로 찾는 문자열을 오른쪽으로 3칸 밀어서 AB를 나란히 놓고, C와 X부터 비교해나갑니다.
그래서 KMP법은 '몇 번째 문자부터 다시 검색할지' 값을 표로 만들어서 문제를 해결합니다. 표를 작성할 때는 패턴에서 겹치는 문자열을 찾습니다. 이 과정에서도 KMP법과 같은 방법을 적용합니다.
① ABCABD 패턴을 위 아래로 놓고 KMP법을 수행합니다.
ABCABD
ABCABD
② 표의 값은 패턴을 오른쪽으로 한 칸씩 밀었을 때 일치하는 문자 수입니다.
③ 코드는 다음과 같습니다.
def kmp_match(txt: str, pat: str) -> int:
pt = 1 # txt 커서
pp = 0 # pat 커서
skip = [0] * (len(pat) + 1) # 건너뛰기 표
# 건너뛰기 표 만들기
skip[pt] = 0
while pt != len(pat):
if pat[pt] == pat[pp]:
pt += 1
pp += 1
skip[pt] == pp
elif pp == 0:
pt += 1
skip[pt] == pp
else:
pp = skip[pp]
# 문자열 검색하기
pt = pp = 0
while pt != len(txt) and pp != len(pat):
if txt[pt] == pat[pp]:
pt += 1
pp += 1
elif pp == 0:
pt += 1
else:
pp = skip[pp]
return pt - pp if pp == len(pat) else -1
KMP법의 pt는 앞으로 나아갈 뿐 뒤로 되돌아오지 않습니다. 하지만 복잡할 뿐만 아니라 보이어-무어법 보다 성능 면에서 같거나 낮은 수준이라 실제 프로그램에서 별로 쓰이지 않습니다.
