문자열 매칭
- 주어진 문자열 S 안에 어떤 패턴문자열 P가 존재하는지, 몇개나 존재하는지, S의 몇번째 인덱스에 있는지 등등을 처리하는 매우 실용적인 문제
- 문자열 매칭을 위한 알고리즘들은 여러가지가 있다. len(S) = N, len(P) = M이라고 하자
- 나이브 매칭 O(NM)
- 노커멘트
-
- 해시 펑션을 이용하기 때문에, 해시 충돌로 오답이 나올 확률이 존재하기는 한다 (거의 없다)
- KMP 알고리즘 O(N+M)
- PS에서 사용되는 표준적인(?) 문자열 매칭 알고리즘.
- Z 알고리즘 O(N+M)
- Z 알고리즘으로도 선형시간에 문자열 매칭이 가능하긴 하다
- Boyer–Moore string-search algorithm 최악 O(NM)
- 평균적으로는 KMP보다 빨라서 실용적으로는 더 선호되지만, 최악을 막는게 중요한 PS계열에서는 사용 불가
- Two-way string-matching algorithm 최악 O(N+M)
- KMP와 보이어무어를 잘 조합해서, 최악 경우에도 선형시간을 유지하도록 만들었다고 한다.
- 파이썬에 내장된 str.__contains__() 또는 str.find() 함수는 3.10 이후부터 Two-way string-matching algorithm 으로 구현되었다고 한다 stackoverflow 게시물
- 따라서 단순히 패턴문자열이 존재하는지, 또는 패턴 문자열의 매칭 위치만 찾고 싶다면, 다 필요없이 그냥 내장 함수를 쓰는것이 가장 빠르고 편리하다.
- 그냥 빠른 정도가 아니라, '압도적으로' 빠르다.
나는 친구가 적다 (Large) 는 원래는 KMP를 의도한 문제로 초기에는 골드~플래티넘에서 기여가 형성되었으나, 파이썬 3.10 업데이트 이후 'in' 연산자 딸깍으로 푸는 것이 가능해지면서 난이도가 드라마틱하게 떨어져서, 현재는 브론즈2 로 난이도가 책정되어있다.
- 하지만, str.find()는, '첫번째' 매칭 위치만 알려준다는 제한이 있다. 오버래핑되는 '모든' 매칭의 위치를 찾기 위해서 str.find()를 반복해서 쓰는것은 O(N^2)이 되므로, 이 경우에는 알고리즘을 구현해야 한다.
- 구현할때는, 라빈-카프 알고리즘 (Rabin-Karp Algorithm), KMP 알고리즘, Z 알고리즘이 다 가능하지만, 일반적으로 KMP 알고리즘이 그냥 제일 무난하고 빠르니까 이거를 쓰자.
세줄 요약
- 존재여부 또는 첫번째 매칭위치만 찾으면 된다면 그냥 내장 str 함수를 쓴다
- 리스트와 같이 문자열이 아닌 시퀀스에서 매칭을 해야 할 경우에도 가능하면 문자열로 변환해서 내장함수를 쓰자.
- 내장함수로 해결이 안될 경우에는 KMP 알고리즘(teflib.string.find) 을 쓴다.
- 대표적으로, '모든' 매칭위치를 찾을때이다.