[알고리즘 종류] 브루트 포스 (Brute Force)

- 브루트 포스

• 패턴 매칭에 사용되는 알고리즘
• 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작
• 시간 복잡도 : O(MN)

# 1.
def bruteforce(p, t):
    M = len(p) # 찾을 패턴의 길이
    N = len(t) # 전체 텍스트의 길이
    
    for i in range(N-M):
        for j in range(M):
            if p[i+j] == t[j]:
                j+=1
            else:
                break
        if j == M:
            return i  # 검색 성공
    return -1 # 검색 실패

# 2.
def bruteforce(p, t):
	M = len(p) # 찾을 패턴의 길이
	N = len(t) # 전체 텍스트의 길이
    i = 0 # t의 인덱스
    j = 0 # p의 인덱스
    while j < M and i < N:
        if t[i] != p[j]:
            i = i - j
            j = -1
        i = j + 1
        j = j + 1
    if j == M : 
        return i - M # 검색 성공
    else:
        return -1 # 검색 실패