단순 구현은 두 문자열을 비교하다가 한 문자라도 틀리면 다음 index로 넘어가서 다시 검사함.

그 전에 검사했던 내용은 버림.

이를 재활용 하는 방법으로는 검사했던 결과를 사용해서 답이 될 수 없는 인덱스는 넘어가는 것

이를 위해서는 오직 ‘현재 시작 위치에서 H와 N을 비교했을 때 몇 글자나 일치했는가’만 알면 된다.

여기서 A와 B가 일치

근데 여기서 시작 위치 i+k 가 답이 되려면 B와 C도 같아야 한다.

그러려면 A와 C가 같아야 한다.

즉, N[…matched-1] (맨 마지막 틀린 1개 뺀 부분 문자열)에서 matched-k의 접두사와 접미사가 같아야 함.

미리 N의 각 접두사에 대해 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해두고 이를 사용하면 됨!

그래서 KMP 알고리즘은 배열 pi[ ]를 미리 계산해둔다.

pi[i] = N[…i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이

이런 식으로!

만약 n글자가 일치한 후 불일치가 발생했을 때 다음으로 시도해야 할 시작 위치는?