컴퓨터알고리즘개론 기말과제 A＋ (문자열 알고리즘의 속도 비교)

1. 소스코드

match = Truefor j in range(m)if text[i + j] != pattern[j]match = Falsebreakif matchprint(f`Pattern found at index {i}`)``` KMP 알고리즘은 Naive 알고리즘의 단점을 보완하기 위해 개발된 알고리즘으로, 패턴 내의 접두사-접미사 정보를 활용하여 검색 속도를 개선한다. KMP 알고리즘은 전체 문자열을 한번만 순회하며, 최악의 경우 O(n+m)의 시간 복잡도를 가진다. 이를 위해 먼저 접미사 배열을 계산하는 함수와 본 검색 함수가 필요하다. 아래 코드는 KMP 알고리즘의 구현이다. m = len(pattern)lps = [0] mlength = 0i = 1while i ` mif pattern[i] pattern[length]length += 1lps[i] = lengthi += 1elseif length != 0length = lps[length - 1]elselps[i] = 0i += 1return lps def kmp_search(text, pattern)n = len(text)m = len(pattern)lps = kmp_preprocess(pattern)i = j = 0while i ` nif pattern[j] text[i]i += 1j += 1if j mprint(f`Pattern found at index {i - j}`)j = lps[j - 1]elif i ` n and pattern[j] != text[i]if j != 0j = lps[j - 1]elsei += 1``` Boyer-Moore 알고리즘은 패턴의 문자를 기준으로 텍스트를 건너뛰면서 …