브루트 포스법

문자열에서 부분 문자열을 검색하는 알고리즘으로 브루트 포스법이 있다.

 

문자열 검색(string searching) 은 문자열 안에 다른 문자열이 포함되어 있는지 검사하고 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다.

 

예를 들면, 문자열 'STRING' 에서 'IN'을 검색하면 검색에 성공하게 된다. 

여기서 검색되는 쪽의 문자열 즉, 'STRING'을 텍스트 (text) 라고 하고 , 찾아내는 문자열 즉 'IN'을 패턴(pattern)이라고 한다.

 

문자열 검색 알고리즘 중에서 가장 기초적이고 단순한 브루트 포스법(brute force method)은 선형 검색을 단순하게 확장한 알고리즘이라서 단순법이라고 한다.

---

브루트 포스법

텍스트 'ABABCDEFGHA' 에서 패턴 'ABC'를 브루트 포스법으로 검색하는 순서 알아보기

 

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

#브루트 포스법으로 문자열 검색하기

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

if __name__ == '__main__':
    s1 = input('Put the text: ')  #텍스트용 문자열
    s2 = input('Put the pattern: ') #패턴용 문자열

    idx = bf_match(s1, s2)         #문자열 s1 ~ s2를 브루트 포스법으로 검색

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