[Algorithm] KMP 알고리즘

KMP 알고리즘

• KMP는 알고리즘을 설계한 Knuth-Morris-Pratt의 앞글자를 하나씩 따서 만든 알고리즘으로 문자열 검색을 효율적으로 할 수 있는 알고리즘이다. (ctrl + f 해서 찾는 검색 알고리즘이 KMP 알고리즘)
• 전체 텍스트의 길이를 N, 찾고자하는 문자열을 M이라 할 때 각 인덱스 별 비교를 하면 시간 복잡도는 O(NM)이지만, KMP 알고리즘을 적용하면 O(N+M)으로 찾을 수 있다.

실패 함수

• KMP 알고리즘의 원리는 실패함수를 이용하는 것이다. 실패 함수란 문자 매칭에 실패했을 때 전체 비교인 O(NM)을 효율적으로 처리하기 위해 건너 뛸 자리를 구하기 위한 함수이다. 즉, 텍스트와 패턴이 불일치 상황에서 접두사 / 접미사가 일치한 최대 길이를 구하여 다음에 건너 뛸 자리를 결정하는 것이다.

전체 문자열이 "ABCCBAABBA" 일 때, 가장 긴 부분 문자열과 그 길이를 담을 실패함수 배열 pi

• 실패 함수를 사용하기 위해선 접두사(prefix)와 접미사(suffix)를 사용하여 prefix == suffix가 될 수 있는 가장 긴 부분 문자열을 배열에 담아야 한다.

• 가장 긴 부분 문자열을 왜 쓸까? 예시로 보자. ABCDABCDABEF 라는 텍스트에서 ABCDABE를 찾는다고 생각해보자. 처음 시작 인덱스를 맞추어서 비교했을 때 각 6번 인덱스가 C,E로 서로 다르기 때문에 원하는 패턴이 아니다. 즉, 실패를 한 상황이다. 이 때 pi[]배열에 가장 긴 부분 문자열을 채운다.

• 중간 단계를 건너 뛰고 현재 단계로 넘어갈 수 있다. i는 텍스트의 현재 비교 위치, j는 패턴의 현재 비교위치를 나타내는 변수로 ABCDAB에서 최대 부분 문자열의 길이는 "AB"인 2(pi[5])이다. 즉, 다음에 비교할 대상은 인덱스4부터 시작이다. 하지만 이미 구해둔 최대 길이는 2 이므로, i와 j는 4에 둘 필요 없이 4 + 2인 6인덱스에 두고 비교를 한다.