문자열 검색 - brute force 알고리즘

2022-02-14

텍스트와 패턴

패턴 : 찾고자하는 문자열
텍스트 : 검색되는 문자열

브루트 포스 알고리즘

책에서는 브루트 포스 알고리즘, 단순법으로 소개되었고,
다른 곳에서는 naïve 문자열 찾기 알고리즘이라고 부르는 듯 하다.

사전에서 검색해보면,
brute : 이성이 없는, force : 힘
이라는 뜻을 찾아볼 수 있다.

brute force = 무지성,
즉 브루트 포스 알고리즘은 문자를 하나하나씩 비교하여 검사하는 방법이다,

브루트포스 알고리즘 동작

텍스트 첫번째와 패턴의 첫번째 글자를 비교한다.
같은 경우, 텍스트와 패턴의 인덱스를 각각 증가해 다음 글자를 검사한다.
다른 경우, 패턴을 한 칸 이동하여 텍스트의 두번째 문자와 패턴의 첫번째 문자를 비교한다.
패턴의 인덱스와 패턴의 길이가 일치하면 텍스트 안에 패턴이 존재. 그렇지 않고 종료되면 패턴이 존재하지 않음

예시.

텍스트 : ABCABDABCBBA 패턴 : ABD

텍스트의 첫번째와 패턴 첫번째 문자 비교. => 일치 텍스트의 두번째와 패턴의 첫번째 비교 => 일치 텍스트의 세번째와 패턴의 세번째 비교 => 불일치

패턴을 한 칸 뒤로 이동하여 다시 검사.

텍스트의 두번째와 패턴의 첫번째 비교 => 불일치

패턴을 또다시 한칸 뒤로 이동

텍스트의 세번째와 패턴의 첫번째 비교 => 불일치

패턴 한 칸 뒤로 이동

텍스트 네번째와 패턴 1 비교 => 일치 …일치 …일치

패턴은 텍스트의 4번째에 존재한다.

알고리즘 (파이썬)

def brute_force(txt, pat): #txt: 텍스트, pat:패턴
    pt=0    #텍스트의 인덱스
    pp=0    #패턴의 인덱스

    while pt!=len(txt) and pp!=len(pat):
        if txt[pt]==pat[pp]:    #문자가 일치하면 인덱스를 증가
            pt+=1
            pp+=1
        else:
            pt=pt-pp+1  #pt의 다음 시작 위치

    return pt-pp if pp==len(pat) else -1    #인덱스를 리턴, 패턴이 존재하지 않는 경우 -1을 리턴

시간복잡도

텍스트의 길이가 n, 패턴의 길이가 m일 때.

최선의 경우 : 패턴의 첫번째 문자가 텍스트에 존재하지 않는 경우
예시 : 패턴이 “FAA”이고, 텍스트는 “DABAACBBDEE”
패턴의 첫번째 문자가 텍스트에 존재하지 않으므로, 각 회전에 첫번째 단계에서 불일치하여 다음으로 넘어감
시간복잡도는 O(n)이 됨
최악의 경우 :
1. 모든 텍스트가 패턴과 일치하는 경우 (텍스트에서 패턴의 모든 위치를 검색하는 경우)
  예시 : 패턴이 “AAA”이고, 텍스트가 “AAAAAAAAAA”
2. 마지막 글자만 다른 경우
  예시: 패턴이 “AAB”이고, 텍스트가 “AAAAAAAAAAB”
시간복잡도는 O(m*(n-m+1))

장단점

단점 : 패턴이 일치하지 않는 경우 다음 스텝에서 패턴의 첫번째부터 다시 검사를 시작하기 때문에 비효율적이다.

chanheelee913

텍스트와 패턴

브루트 포스 알고리즘

알고리즘 (파이썬)

시간복잡도

장단점