[알고리즘] 브루트 포스법

브루트 포스법은 어떤 문자열에서 특정한 패턴을 찾을 때까지 일일히 문자를 대조해 보는 알고리즘이다.

당연히 연산 횟수가 무지막지하게 많으며, 일반적으로 시간 복잡도는 O(M * N)으로 알려저 있다.

(패턴의 길이: M, 텍스트의 길이: N)

 

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

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)}번째 문자가 일치합니다.')