7-1 브루트 포스법 & 7 - 2 KMP법 7-3 보이어-무어법

문자열 검색

어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것

텍스트 : 검색되는 쪽의 문자열

패턴 : 찾아내는 문자열

 

1.브루트 포스법 = 단순법

선형검색을 단순하게 확장한 알고리즘

 

문자가 일치하는 동안 차례로 계속 검사. 그러나 다른 문자를 만나면 더이상 검사를 중단하고 다음 인덱스로 패턴의 첫번째문자부터 처음부터 다시 검사를 한다.

단순 알고리즘이나 매우 빠르게 동작한다.

# 브루트 포스법으로 문자열 검색하기
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

if __name__ == '__main__':
    s1 = input('텍스트를 입력하세요.: ')  # 텍스트용 문자열
    s2 = input('패턴을 입력하세요.: ')  # 패턴용 문자열

    idx = bf_match(s1,s2)  # 문자열 s1 ~ s2를 브루트 포스법으로 검색
    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')

    else:
        print(f'({idx} + 1)번째 문자가 일치합니다.')

    idx = bf_match(s1,s2)

    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{(idx+1)}번째 문자가 일치합니다.')

* 멤버십 연산자로 구현하기

멤버십 연산자 

어떤 문자열이 다른 문자열 안에 포함되어있는지 검색 >> 포함여부는 알 수 있으나, 그 위치는 알지 못한다.

ptn in txt  # ptn은 txt에 포함되어있습니까?
ptn not in txt  # ptn은 txt에 포함되어 있지 않습니까?

2. KMP법

텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴의 이동을 되도록이면 크게 하는 알고리즘

비교가 필요하지 않은 부분은 건너뛰고, 비교가 필요한 부분만 비교함으로써 성능을 개선하는 알고리즘

'몇번째 문자부터 다시 검색할지의 값'을 표로 만들어서 문제를  해결

패턴을 위아래로 나란히 놓고 아래쪽 패턴을 오른쪽으로 1칸 밀어 서로 겹친다. 패턴의 첫 문자와 마주보는 위치가 일치하지 않을경우, 패턴을 오른쪽으로 1칸 민다. 마찬가지로 패턴[0]과 마주보는 텍스트가 일치하지 않으면 오른쪽으로 1칸 민다. 일치하는 부분이 생길 경우, 건너뛰기 표에 겹치는 수만큼 1 , 2 , 3..을 표기한다. 겹치는 만큼 건너뛰고 검색을 반복

# 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):
        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

if __name__ == '__main__':
    s1 = input('텍스트를 입력하세요.: ')  # 텍스트용 문자열
    s2 = input('패턴을 입력하세요.: ')  # 패턴용 문자열

    idx = kmp_match(s1,s2)  # 문자열 s1 ~ s2 까지를 KMP법으로 검색

    if idx == -1:
        print("텍스트 안에 패턴이 존재하지 않습니다.")
    else: 
        print(f'{idx+1}번째 문자가 일치합니다.')

3.보이어-무어법

패턴의 마지막 문자부터 첫번째 문자의 순서로 검색을 진행

패턴의 길이 : n

패턴에 포함되지 않는 문자를 만난경우

패턴 이동량이 곧 n. 

패턴에 포함되는 문자를 만난 경우

마지막에 나오는 위치의 인덱스가 k 이면 이동량은 n - k - 1

같은 문자가 패턴 안에서 중복하여 존재하지 않을 경우 패턴의 끝 문자의 이동량은 n이다.

# 보이어 무어법으로 문자열 검색하기(문자열 길이는 0~255개)

from pprint import pp


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를 보이어,무어법으로 검색
    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{idx + 1}번째 문자가 일치합니다.')