(PYTHON)파이썬 알고리즘 - 문자열 검색(블루투 포스법, KMP법, 보이어 무어법)

(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)파이썬' 카테고리의 글 목록