이즈미르의 프로그래밍

저번 문자열 검색 알고리즘 1편에서 Naive, Rabin Karp, KMP를 알아보았었다. 2020/04/16 - [알고리즘] - 문자열 검색 알고리즘 1편 (Naive, Rabin Karp, KMP) 문자열 검색 알고리즘 1편 (String searching algorithm) 이번에 알아볼 알고리즘은 문자열 검색 알고리즘이다. 이름 그대로 본문 문자열(haystack)에서 찾고자 하는 특정 문자열(pattern)의 위치를 찾는 알고리즘이다. 문자열 검색 알고리즘으로 따로 언급할 만큼 많은.. izmirprogramming.tistory.com 이번 시간에는 Boyer Moore 알고리즘을 알아보도록 하자. 실제로 가장 많이 사용되고 있는 문자열 검색 알고리즘이 바로 Boyer Moore 알고리즘이라..

이번에 알아볼 알고리즘은 문자열 검색 알고리즘이다. 이름 그대로 본문 문자열(haystack)에서 찾고자 하는 특정 문자열(pattern)의 위치를 찾는 알고리즘이다. 문자열 검색 알고리즘으로 따로 언급할 만큼 많은 연구가 이뤄지고 있다. 종류는 대표적인 것들로 아래와 같이 4가지가 있다. Naive Rabin Karp KMP (Knuth-Morris-Pratt) Boyer Moore 1~3번 문자열 검색 알고리즘을 1편에서 설명하고 4번 문자열 검색 알고리즘을 2편에서 설명하려고 한다. 먼저 Naive부터 알아보자. 1. Naive Naive 방식은 본문 처음부터 끝까지 문자 하나하나씩 패턴과 비교하여 찾는다. 따로 설명하지 않아도 쉽게 구현할 수 있을 것이다. 코드로 표현하면 아래와 같다. std::..