알고리즘 - 브푸트 포스법 (문자열 검색)

 

문자열 검색(string search)은 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다. 검색되는 쪽의 문자열을 text, 찾아내는 문자열을 pattern이라고 한다.

---

 

브루트 포스

브루트 포스법(brute force method)이란 선형 검색을 단순하게 확장한 알고리즘이라서 단순법이라고 한다. 예를 들어 텍스트 'ABABCDEFGHA'에서 패턴 'ABC'를 브루트 포스로 검색하는 순서를 알아보자.

 

A. 텍스트의 첫 문자 'A'에서 시작하는 문자 3개가 패턴과 일치하는지 검사한다. A와 B는 일치하지만 C가 일치하지 않는다.

B. 패턴을 오른쪽으로 1칸 밀고, 텍스트의 2번째 문자와 그 이후 부분이 일치하는지 검사한다. 불일치.

C. 패턴을 다시 1칸 민다. 패턴과 텍스트의 문자가 일치하므로 검색에 성공한다.

 

브루트 포스법은 이미 검사한 위치를 기억하지 못하므로 효율이 좋지 않다.

 

<code>

# -- brute force match

def bf_match(txt, pat):
    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

 

 

파이썬의 멤버십 연산자(membership operator)인 in과 not in은 포함 유무는 확인할 수 있지만 위치는 확인할 수 없다.