#브루트 포스 (Brute Force)

#브루트 포스

검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회하며 문자들을 일일히 비교하는 방식의 알고리즘.

비교하고자 하는 문자열과 패턴을 한칸씩 이동하면서 비교하여 일치 여부를 확인한다.

 

#비교 과정

T : 원본 문자열

P : 찾고자 하는 문자열 패턴

 

1. t,p 모두 첫 문자부터 비교를 시작하므로 검색 인덱스를 맨 처음 인덱스로 설정한다.

 

2. 각각의 검색 인덱스부터 하나씩 문자를 비교한다.

2-1. 비교문자가 같으면 t,p 인덱스모두 뒤로 한칸씩 이동

2-2. 비교문자가 다르면 t의 인덱스는 한칸 뒤로 이동하고, p의 인덱스는 맨 처음으로 돌아간다.

 

3. 2과정부터 검색이 끝날때까지 반복한다.

 

#파이썬 코드

ㅡ 비교대상 문자열의 끝까지 비교하거나, 패턴을 찾을때까지 반복해서 문자를 하난씩 차례로 비교한다

ㅡ 원본 문자열에서 패턴이 속한 위치를 반환한다.

def BruteForce(p,t):
	i=0
    j=0
    while i < len(t) and j < len(p)
    	if t[i] != p[j]:
     		i=i-j
        	j=-1
    	i+=1
    	j+=1
    if j==len(p):
    	return i-len(p)
    else:
    	return -1

pattern="mutsa"
text = "best is mutsa"
print(BruteForce(pattern,text))