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 이다.