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