📂 알고리즘/문자열

보이어-무어(Boyer-Moore) 알고리즘

1. 개념 📸 보이어-무어(Boyer-Moore) 알고리즘은 skip이라는 것을 활용한 문자열 매칭 알고리즘이다. 여기서 skip이란 문자열을 비교할 때 불필요한 비교가 있다면 건너뛸 수 있도록 도와주는 것이다. (정확한 명칭은 아니지만 아래의 동작방식을 본다면 왜 skip이라고 불리는지 알 수 있을 것이다.) 보이어-무어 알고리즘은 문자열을 비교할 때 일반적으로 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 그래서 비교할 문자열과 패턴을 앞부분부터 확인하는 것이 아닌 뒷부분부터 확인하게 된다. 2. 동작방식 🎬 기본적인 동작방식은 일치하지 않은 문자를 만난 경우 패턴에서 일치하는 문자를 찾아서 이동한 후 비교를 다시 시작한다는 것이다. 본문은 'abphone' 패턴은 'phon..

라빈-카프(Rabin-Karp) 알고리즘

1. 개념 ⚽ 라빈-카프(Rabin-Karp) 알고리즘이란 해싱(Hashing)을 이용한 문자열 매칭 알고리즘이다. 비교하고자 하는 문자들과 패턴의 문자들을 일일이 비교하는 대신에 문자열의 해시값을 비교하는 방식으로 진행된다. 2. 동작방식(연습용) 🏀 동작 방식은 아래와 같다. 해시 함수를 설정한다. 해시 함수를 이용하여 패턴의 해시값을 구한다. 비교하고자 하는 문자열의 해시값을 구한다. 일치하면 패턴과 찾은 문자열을 1:1 비교한다. 일치하지 않으면 비교하고자 하는 문자열을 한 칸 뒤로 옮겨서 3번부터 다시 시작한다. 해시값이 같더라도 1:1 매칭을 통해서 최종적으로 패턴과 비교하고자 하는 문자열이 일치하는지 확인하는 절차가 필요하다. 그 이유는 해시값이 같다고 해서 무조건 같은 문자열이라고 보장할 ..