[기본 알고리즘] 문자열 매칭 알고리즘 (완전탐색 VS KMP VS 라빈 카프)

 a b c d e f g e t f 라는 m문자열에 e f g e 라는 n문자열이 존재하는지 확인한다고 하자.

문자열 매칭에서 기억해야할 점은 O(n)으로 풀이가 가능하다는 점이다.

 

1) brute force

for문을 통해 모든 경우를 탐색한다면, O(n * m)의 시간복잡도를 가진다.

 

2) KMP 알고리즘

구현이 까다로운 알고리즘이다. O(n)의 시간복잡도를 가진다.

 

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

해시와 슬라이딩윈도우를 사용한 알고리즘이다. O(n)의 시간복잡도를 가진다.

KMP 알고리즘에  비해 구현이 쉽기 때문에, 알고리즘 문제에서 사용하기 적합해보인다.

https://m.blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=kks227&logNo=220927272165&proxyReferer=