BruteForce

BruteForce

• 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작
• 최악의 경우 시간복잡도는 텍스트의 모든 위치에서 패턴을 비교해야하므로 O(MN)이 됨

def BruteForce2(p,t) :
    n = len(t)
    m = len(t)
    cnt = 0
    for i in range(n-m + 1) :
        match = 0
        for j in range(m) :
            if t[i+j] != p[j]:
                break
            else :
                match +=1
        if match == m :
            cnt += 1

    return cnt

1. 길이-패턴 +1만큼 (인덱스 에러 방지)
2. 패턴을 돌며 텍스트의 i+j번째가 패턴의 j번째와 다르면 for문 멈춤
3. 일치하면 계속
4. j가 m-1과 같으면
5. 일치하는 것으로 간주