KMP (1) 썸네일형 리스트형 [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 밑에 보이는 예시는 KMP 알고리즘 사용 전인데 효율이 떨어져 보입니다. 텍스트와 패턴이 일치하는지 차례대로 순회하면서 비교해보기 때문에 시간복잡도는 O(문자열 길이 * 패턴 길이) = O(N)으로, 시간이 오래 걸립니다. KMP 알고리즘이란? 패턴과 텍스트의 불일치를 감지할 때마다 그 전에 검사해왔던 텍스트의 문자들이 무엇인지 알고 있습니다(처음 검사할 때 A B A B 로 B에서 불일치가 발생했을 때, 불일치 발생 전 문자들이 A, B, A). KMP 알고리즘은 이를 이용해 불필요한 검사는 스킵합니다. 시간 복잡도는 최악의 경우, O(문자열 길이 * 패턴 길이) 이므로 위와 같이 O(N)입니다. 알고리즘 구성 lps[ ] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대 길이를 저장하는 배열 (밑에.. 이전 1 다음
