반응형
(PYTHON)파이썬 알고리즘 - 문자열 검색(블루투 포스법, KMP법, 보이어 무어법)
브루투 포스법
def bf_match(txt: str, pat: str) -> int:
"""브루트 포스법으로 문자열 검색"""
pt = 0 # txt(텍스트)를 따라가는 커서
pp = 0 # pat(패턴)를 따라가는 커서
while pt != len(txt) and pp != len(pat): # pt와 pp가 문자열 끝자리를 벗어나지 않았다면 실행
if txt[pt] == pat[pp]: #텍스트문자열과 패턴용 문자열의 pt, pp위치에 값이 같으면
pt += 1
pp += 1
else: # 값이 다르면
pt = pt - pp + 1 # 비교할 시작값(pt)을 배열 한칸 우측으로 이동
pp = 0 # pp 시작값은 0번으로 변경하여 다시 비교
return pt - pp if pp == len(pat) else -1 # 만약 비교할 패턴이 다맞아서pp가 pat길이와 같은 값이되면 pt - pp를 리턴, 아니면 -1을 리턴
if __name__ == '__main__':
s1 = input('텍스트를 입력하세요.: ') # 텍스트용 문자열
s2 = input('패턴을 입력하세요.: ') # 패턴용 문자열
idx = bf_match(s1, s2) # 문자열 s1~s2를 브루트 포스법으로 검색
if idx == -1:
print('텍스트 안에 패턴이 존재하지 않습니다.')
else:
print(f'{(idx + 1)}번째 문자에서 일치합니다.')
표준라이브러리를 사용한 문자열 검색(find, index)
# 문자열에 포함되어 있는 문자열을 검색(find 계열 함수）
txt = input('문자열 txt: ') # 문자열 나열
ptn = input('문자열 ptn: ') # 검색할 문자
c = txt.count(ptn)
if c == 0: # 포함된 문자가 없음
print('ptn은 txt에 포함되어 있지 않습니다.')
elif c == 1: # 포함된 문자가 １개만 있는 경우
print('ptn이 txt에 포함되어 있는 인덱스: ', txt.find(ptn))
else: # 포함된 문자가 2개 이상 있는 경우
print('ptn이 txt에 포함되어 있는 맨 앞 인덱스: ', txt.find(ptn))
print('ptn이 txt에 포함되어 있는 맨 끝 인덱스: ', txt.rfind(ptn))# 문자열에 포함되어 있는 문자열을 검색(index 계열 함수)
txt = input('문자열 txt: ')
ptn = input('문자열 ptn: ')
c = txt.count(ptn)
if c == 0: # 포함된 문자가 없음
print('ptn은 txt에 포함되어 있지 않습니다.')
elif c == 1: # 포함된 문자가 １개만 있는 경우
print('ptn이 txt에 포함되어 있는 인덱스: ', txt.index(ptn))
else: # 포함된 문자가 2개 이상 있는 경우
print('ptn이 txt에 포함되어 있는 맨 앞 인덱스: ', txt.index(ptn))
print('ptn이 txt에 포함되어 있는 맨 끝 인덱스: ', txt.rindex(ptn))
KMP법
브루트 포스법은 일치하지 않는 문자를 만나면 이전 단계를 검사했던 결과를 버리고 패턴의 첫 문자부터 다시 검사를 수행하지만, KMP법은 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘입니다.
(건너뛰기 표를 만들어 활용)
def kmp_match(txt: str, pat: str) -> int:
"""KMP법에 의한 문자열 검색"""
pt = 1 # txt를 따라가는 커서
pp = 0 # pat를 따라가는 커서
skip = [0] * (len(pat) + 1) # 건너뛰기 표
# 건너뛰기 표 만들기
skip[pt] = 0
while pt != len(pat): # pt 위치가 패턴길이와 같지 않다면 실행
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): # pt와 pp가 문자열 끝자리를 벗어나지 않았다면 실행
if txt[pt] == pat[pp]: #텍스트문자열과 패턴용 문자열의 pt, pp위치에 값이 같으면
pt += 1
pp += 1
elif pp == 0: # pp가 0이면
pt += 1
else:
pp = skip[pp]
return pt - pp if pp == len(pat) else -1 # 만약 비교할 패턴이 다맞아서pp가 pat길이와 같은 값이되면 pt - pp를 리턴, 아니면 -1을 리턴
if __name__ == '__main__':
s1 = input('텍스트를 입력하세요.: ') # 텍스트용 문자열
s2 = input('패턴을 입력하세요.: ') # 패턴용 문자열
idx = kmp_match(s1, s2) # 문자열 s1~s2를 KMP법으로 검색
if idx == -1:
print('텍스트 안에 패턴이 존재하지 않습니다.')
else:
print(f'{(idx + 1)}번째 문자에서 일치합니다.')
보이어 무어법
패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행합니다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정합니다.
def bm_match(txt: str, pat: str) -> int:
"""보이어 무어법에 의한 문자열 검색"""
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 \
else len(pat) - pp
return -1
if __name__ == '__main__':
s1 = input('텍스트를 입력하세요.: ') # 텍스트 문자열
s2 = input('패턴을 입력하세요.: ') # 패턴 문자열
idx = bm_match(s1, s2) # 문자열 s1~s2를 KMP법으로 검색
if idx == -1:
print('텍스트 안에 패턴이 존재하지 않습니다.')
else:
print(f'{(idx + 1)}번째 문자에서 일치합니다.')
(PYTHON)파이썬 전체보기
'(PYTHON)파이썬' 카테고리의 글 목록
전산 관련 경험을 기록 하는 곳
reddb.tistory.com
반응형
'(PYTHON)파이썬' 카테고리의 다른 글
| (PYTHON)파이썬 알고리즘 - 연결리스트(LinkedList), 원형이중리스트 (0) | 2021.03.31 |
|---|---|
| (PYTHON)파이썬 알고리즘 - 힙정렬, 도수정렬 (0) | 2021.03.28 |
| (PYTHON)파이썬 알고리즘 - 병합정렬 (0) | 2021.03.19 |