브루트 포스법

• 문자열 검색 알고리즘 중에서 가장 기초적이고 단순한 방법
• 선형 검색을 단순하게 확장한 알고리즘으로 단순법이라고도 함
  
• 이미 검사한 위치를 기억하지 못하므로 브루트 포스법은 효율이 좋지 않음

문자열 검색

• 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함돼 있으면 어디에 위치하는지 찾아내는 것
• 텍스트 : 검색되는 쪽의 문자열
• 패턴 : 찾아내는 문자열

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

KMP법

• 브루트 포스법과 달리 검사했던 결과를 버리지 않고 활용하는 알고리즘
• 패턴 2개를 나란히 놓고 아래쪽 패턴을 오른쪽으로 1칸 밀어 건너뛰기 표를 만들어야함
  

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

• 보이어 무어보다 성능 면에서 같거나 오히려 낮은 수준이라서 실제 프로그램에서 별로 사용하지 않음

보이어 무어법

• 패턴의 끝문자에서 시작해 앞쪽을 향해 검사를 수행
• 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정
  
  

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