Algorithm/Pattern Searching (3) 썸네일형 리스트형 [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(2) 앞서 Boyer-Moore 알고리즘에 사용되는 두 원리 중 Bad Character 원리를 살펴 보았다. 이번에는 그 나머지 원리인 Good Suffix 원리를 배워보려고 한다. 2021.07.26 - [Algorithm/Pattern Searching] - [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글 2021.07.23 - [Algori bblackscene21.tistory.com .. [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글 2021.07.23 - [Algorithm/Pattern Searching] - [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 이 알고리즘을 이 두 가지 접근법을 조합한 것입니다. 각각의 접근법에 대해 패턴을 처리하고, 검색을 수행할 때 두 접근법이 제안하는 값 중 최대값만큼 패턴을 이동합니다. (두 가지 원리 모두 각각 독립적으로 사용해도 문자열 검색이 가능합니다.) 1) Bad Character 2) Good Suffix 이번 글에서는 Bad Character 원리부터 살펴보겠습니다. .. [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 밑에 보이는 예시는 KMP 알고리즘 사용 전인데 효율이 떨어져 보입니다. 텍스트와 패턴이 일치하는지 차례대로 순회하면서 비교해보기 때문에 시간복잡도는 O(문자열 길이 * 패턴 길이) = O(N)으로, 시간이 오래 걸립니다. KMP 알고리즘이란? 패턴과 텍스트의 불일치를 감지할 때마다 그 전에 검사해왔던 텍스트의 문자들이 무엇인지 알고 있습니다(처음 검사할 때 A B A B 로 B에서 불일치가 발생했을 때, 불일치 발생 전 문자들이 A, B, A). KMP 알고리즘은 이를 이용해 불필요한 검사는 스킵합니다. 시간 복잡도는 최악의 경우, O(문자열 길이 * 패턴 길이) 이므로 위와 같이 O(N)입니다. 알고리즘 구성 lps[ ] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대 길이를 저장하는 배열 (밑에.. 이전 1 다음
