====== KMP 알고리즘 ======

  * 기본적으로 KMP 알고리즘은 문자열 매칭을 선형시간에 해결해주는 알고리즘이다. 
  * KMP 알고리즘에서는 문자열 매칭을 위해서 fail 함수라는 것을 정의해서, 패턴 P에 대한 fail함수의 table을 구하고, 이를 이용해서 스트링 S에서 P의 모든 occurrence를 효율적으로 찾는다.
    * fail함수를 pi배열이라고도 부른다
  * 문자열 검색은 실용적으로 너무나 흔하고 중요한 기능이므로, 이 기능이 가장 중요하게 생각되는 것은 당연하다. 그래서 KMP 알고리즘에 대한 보통의 설명은 다음 순서로 진행되는거 같다,
    * 문자열을 빠르게 매칭하기 위해서는 이러이러한 불필요한 과정을 줄일수 있으면 좋을거 같아 => 이런 형태의 테이블이 있다고 생각하자. 그러면 그 테이블을 갖고서 이런 방법으로 매칭하면 불필요한 과정을 줄여서 O(m+n)에 매칭이 될거 같아 => 이 테이블을 만드는 방법도 매칭할때의 알고리즘을 비슷하게 적용하면 O(m)에 만들수 있을거 같아 => 오 이렇게 해서 O(m+n) 매칭이 되는구나
  * 하지만, PS쪽에서는 문자열 매칭 자체보다는 fail 함수의 특징을 이용해서 활용하는 능력이 더 중요해보인다..
    * 문자열 매칭으로는 여기에서 뭔가 응용/변형을 해서 문제를 만들기가 좀 어려운거 같다.
  * 다시 말하면, fail 테이블을 구하는 과정보다도 fail 테이블을 O(n)에 구해 놓은 상태에서, 이걸 어떻게 활용해서 문제에서 원하는 값을 구할것인가가 더 중요한 느낌이긴 하다.
    * 이 관점으로는 문자열 매칭문제도 이렇게 바꿔서 해결할수 있다.
      * (n=len(P)라고 할때) P#S 에 대해서 fail 함수를 구한 다음에, fail[i] == n이 되는 i를 모두 찾으면 된다. S[i-n*2:i-n] == P 이다.
  * 그럼 진짜로 fail 함수를 활용해서 어떤 문제를 풀수 있을지는 [[ps:문자열]]쪽에서 설명.

===== 구현 =====
  * 알고리즘이 매우 컴팩트하게 구현되는 편이라서, 사람들마다 코드 차이가 별로 없을것 같다
  * failure table을 만드는 함수와, failure table를 이용해서 매칭을 하는 함수를 분리해서 만들었다
  * 코드
    * [[:ps:teflib:string#failure_table|teflib.string.failure_table]]
    * [[:ps:teflib:string#failure_table|teflib.string.find]]

===== 벤치마크 =====
  * [[ps:problems:boj:1305]]: fail 함수를 구하는 문제. n≤1,000,000, 수행시간 248ms (1등: 216ms)
  * [[ps:problems:boj:1786]]: 매칭 문제. n,m≤1,000,000, 수행시간 520ms (1등: 492ms)