[Algorithm] 단순 문자열 매칭 알고리즘

 

 

33강에 대한 리뷰

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12362

알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지

 

 

하나 씩 확인하는 가장 단순한 알고리즘

 

단순히 모든 위치에서 모든 문자열이 같은지 확인하므로 O(N*M)의 시간복잡도를 가짐

 

효율적이진 않음

 

 

** Python

 

def find_string(parent, pattern):
    parent_len = len(parent)
    pattern_len = len(pattern)
    for i in range(parent_len - pattern_len):
        found = True
        for j in range(0, pattern_len):
            if j < pattern_len and parent[i + j] != pattern[j]:
                found = False
                break
        if (found):
            return i
    return -1
    
if __name__ == "__main__":
    p = "Hello World"
    t = "llo W"
    result = find_string(p,t)
    if result == -1:
        print("Not found")
    else:
        print(f'{result + 1}번째에서 찾았습니다.')