문자열 패턴 매칭 brute force 알고리즘

1. brute force 패턴 매칭 알고리즘

 

원본 문자열 s에 대하여 특정 문자열 패턴 p가 몇번이나 존재하는지 찾고자 하는 알고리즘

 

모든 경우의 수를 검사하여 몇번이나 패턴이 존재하는지 검사한다

 

이때 패턴과 해당 길이의 부분 문자열을 전부 비교하는게 아니라 한글자 한글자씩을 비교함

 

예를 들어

 

s = abcdefghi

 

p = cdf 라고 한다면

 

abcdefghi

cdf

 

부터 비교를 시작.. abc와 cdf를 한번에 비교하는게 아니라 a와 c를 비교하여

 

a와 c가 다르므로 cdf를 한칸 뒤로 민다

 

내 생각에 abc와 cdf를 한번에 비교하는 시간보다 a와 c를 비교하고 한칸 뒤로 미는게 효과적이라 그런가??

 

아닌데..? 일단 한글자씩 비교한다고 배웠으니까 그렇게 알아놓자고

 

아무튼

 

abcdefghi

  cdf

 

그러면 b와 c가 다르니까 다시 1칸 밀어..

 

이런식으로 모든 경우를 검사하는 brute force 패턴 매칭 알고리즘

 

 

2. 구현 예시

 

p = 'is' #찾고자 하는 패턴

t = 'This is a book~!' #원본 텍스트

M = len(p) #패턴의 길이
N = len(t) #원본 텍스트의 길이

def BruteForce(p,t):
    
    i = 0 #원본의 인덱스
    j = 0 #패턴의 인덱스

    while j < M and i < N:
        
        if t[i] != p[j]: #원본과 패턴의 글자가 서로 다르다면
            
            i = i - j
            j = -1
        
        i = i + 1 #인덱스를 오른쪽으로 1칸씩 이동하면서 비교
        j = j + 1
    
    if j == M: #j가 무사히 M까지 이동했다면...
        
        return True #패턴이 1번이라도 존재한다
    
    else:
        
        return False #패턴이 단 1번도 존재하지 않는다

print(BruteForce(p,t))

 

i = i + 1, j = j + 1로 1칸씩 오른쪽으로 이동시키면서, 1글자 1글자씩 패턴과 원본을 비교하는데 만약 서로 다르다면

 

i는 i-j로 초기화하고 j는 -1로 초기화하는게 특이하다

 

별로 와닿지 않으니까 한번 하나씩 생각해보면

 

 

처음에 틀렸으니까 i-j = 0으로 i에 넣고, j는 -1을 넣고... 다시 1씩 더해주면 i는 1이 되고 j는 0이 된다

 

 

두번째에도 틀렸으니까 i-j = 1을 i에 넣고 다시 1을 더해주고 j에 -1을 넣고 j에 1을 더해줘서 0이 되는데..

 

이게 무슨 의미냐

 

맨 처음에 비교를 시작하면 i=0, j=0 >> i=1, j=1 .>>> i=2, j=2 >>>여서 어디서 틀리든 i-j가 항상 0이 된다

 

그리고 다음 비교에 시작하면 1을 더해주므로 i는 1부터 시작할 수 있다

 

반면 j는 항상 -1을 넣은 뒤에 1을 더해주므로.. 항상 패턴 j는 0부터 시작할 수 있다

 

마찬가지로 두번째 비교에 들어가면 i=1, j=0 >> i=2, j=1 >>> i=3, j=2 >>> 여서 i-j는 1이 되어서 다음 비교에

 

i=2부터 시작할 수 있다

 

마찬가지로 i=2, j=0 >>> i=3, j=1 >>> 이여서 i-j=2가 되니까 다음 비교에서 i=3부터 시작할 수 있다

 

i-j는 이러한 의미를 가지고 있다

 

 

3. 특징

 

최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교하여 O(MN)까지 가능하다

 

이러한 비교횟수를 줄이고자 KMP, 보이어-무어 알고리즘 등이 개발되었다

 

 

4. 예시문제

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14P0c6AAUCFAYi&categoryId=AV14P0c6AAUCFAYi&categoryType=CODE&problemTitle=string&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

주어진 원본 문자열에서 특정한 패턴이 몇번이나 나오는지를 구하는 프로그램 작성

 

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
     
    t = input()
     
    p = input()
     
    m = len(p)
     
    o = input()
     
    n = len(o)
     
    cnt = 0
     
    i = 0
     
    while i < n:
         
        j = 0
         
        while i < n and j < m:
 
            if o[i] != p[j]:
                i = i - j
                j = -1
            i += 1
            j += 1
 
        if j == m:
 
            cnt += 1
     
    print('#'+t,cnt,sep=' ')

 

pattern과 original 문자열을 각각 받고, 각각의 길이를 구한다

 

몇번이나 등장하는지 나타내는 cnt를 초기화하고, 각각의 시작 index i,j를 초기화한다

 

그리고 단 1번만 찾는 것이 아니고 여러번 찾고자 하기 때문에 i와 j에 대한 시작 초기화를 잘 생각해야한다

 

i=0을 초기화하고 while i < n:을 수행

 

안에서 j=0으로 초기화하고, 첫번째 패턴매칭을 수행

 

while i < n, j<m을 수행하고, 만약 서로 다른 글자가 나타난다면 i = i-j, j=-1로 초기화하고, i,j에 1씩 더한다음에 반복을 계속 수행

 

모든 반복을 수행했을 때 j가 M이라면, 패턴을 1번 찾았으므로 cnt에 1을 더해준다

 

그런데 i가 n보다 작다면, 모든 원본 문자열을 검색한 것이 아니므로, 또 존재하는지, 다시 한번 반복을 수행