KMP
KMP는 길이가 긴 문자열에서 어떤 짧은 문자열이 몇 번 나타나는지 선형시간에 확인할 수 있는 알고리즘이다.
0부터 i번째 까지 맞고 i+1번째에서 틀렸다면 0부터 i번째 까지 맞았다는 정보를 이용하여 탐색을 개선할 수 있다. 다음 그림을 보자.
abcab까지는 맞지만 c와 x가 다르다. 이때 여태까지 맞은 abcab를 잘 보자. abcab에서 접두사면서 접미사인 최대 길이 문자열은 ab이다. 이제 밑의 문자열을 오른쪽으로 세칸 움직여서 ab를 일치시킨 후 탐색을 재개하면 된다. 이렇게 하면 위의 문자열에서 문자를 보는 위치가 감소하지 않고 계속 증가하기 때문에 수행시간이 빨라진다.
이를 위해 구해야 하는 것이 실패함수이다. fail[i]는 문자열 S의 부분 문자열인 S[0,i]에서 접두사이면서 접미사인 최대 문자열의 길이이다. (단, S[0,i] 제외)
fail[i]를 계산 할 때에 fail[i-1]값을 이용할 수 있다. fail[i-1]=x라 하자. 즉, S[0,i-1]에서 S[0,x-1]=S[i-x,i-1]이다. S[x]=S[i]면, fail[i]=fail[i-1]+1이다. 만약 그렇지 않다면 fail[x-1]를 확인해본다. 이렇게 재귀적으로 될 때까지 찾으면 실패함수를 구할 수 있다.
매 단계마다 실패함수 값이 최대 1씩 증가하는데 각 실패함수를 구하기 위해 확인하는 실패함수 값은 작아지기만 하고 처음에 본 실패함수 값보다 더 작아질 수 없기 때문에 시간복잡도가 \(\BigO{N}\)임을 알 수 있다.
KMP를 할 때에도 비슷한 방법을 사용한다. 문자열 H에서 S를 검색할 때, i번째에서 매칭에 실패할 경우 fail[i]값을 보고 매칭을 다시 시도한다. fail[i]=x라 하면, 문자열 H에서 현재 보고 있는 문자와 S[x]가 같은지를 비교하는 것이다. 실패할 경우 fail[x]값을 보고 될 때까지 매칭을 다시 시도한다. 이 작업 역시 문자열이 일치한 길이가 최대 1씩 증가하는데 불일치할 경우 실패함수를 보며 길이가 줄어들기만 하고 길이가 처음에 일치한 길이보다 더 줄어들 수 없기 때문에 시간복잡도가 \(\BigO{N}\)이 된다.