KMP 알고리즘 완벽 정리

 KMP 알고리즘이 어떻게 되는 지 찾다 보면 여러 블로그에서 어떻게 되는 지 설명해 주기는 하는 데, 조금씩 다 달라서 오히려 헷갈리더라. 그래서. 오늘은 헷갈리는 부분에 대한 KMP알고리즘의 전체적인 정리를 해보려고 한다.

KMP알고리즘이란

KMP알고리즘이란 쉽게 말해 일일이 확인하던 문자열 string의 불필요한 탐색 시간을 좀 더 효율적으로 줄이기 위해 나타난 방법이다. 예를 들어 ababcaba 라는 문자열이 있다고 치자.

ababcaba 문자열 테이블 만들기

이 문자열의 반복되는 정도를 확인하기 위해 테이블을 만든 다. 이 블로그 하나로 이해가 되길 바란다. 테이블이 만들어 지는 조건은 다음과 같다.

1. 접두사(i)와 접미사(j)가 같다면 숫자가 1올라간다.
2. 그 전 접두사와 접미사가 일치 후, 그 다음 찾으려는 문자가 일치하지 않다면, (i)를 0으로 이동 후, 그 문자와 비교를 하는 데, 그래도 맞지 않다면, 0. 일치하다면 1 유지한다.

이렇게만 생각하면 된다. 조금 더 이해를 돕고자 ababcaba를 예를 들어 설명하겠다.

• a는 (i, j)가 같은 위치에 있으므로 비교 대상이 없어서 0.
• a(i), b(j)는 접두사 접미사가 나눠지지만 i와 j가 같지 않으므로 0. 그리고 j 이동
• a(i), b, a(j)는 i와 j가 같으므로 1. 그리고 i와 j 이동
• a, b(i), a, b(j) 또한 i, j가 같으므로 2. 그리고 i, j 이동
• a, b, a(i), b, c(j) 는 같지 않아 0으로 되돌리기 전, i를 다시 인덱스[0] 번째 a와 비교 하는 데, 그래도 같지 않으므로 0...

문자열 테이블

이렇게 해서 테이블 결과는 ababcaba(00120123) 이 된다.

찾으려는 문자열이 찾아지게 되는 과정

ababcaba의 문자열을 가지고, ababcadababcabdababcaba의 문자열에서 찾으려고 한다. 문자열을 찾는 방법은 다음과 같이 진행된다고 보면된다.

1번

2번

1. 우선 1번을 보면, 6번째 인덱스에서 일치하지 않는 것이 확인되면, 그 전 (인덱스 5번)문자의 테이블을 확인한다.
2. 5번 인덱스의 테이블이 1이니, 1번 인덱스와 다시 비교한다.
3. 1번 인덱스 또한 불일치로 확인 되어, 그 전(인덱스 0번)문자의 테이블을 확인한다.
4. 0번 인덱스의 테이블 또한 불일치로, 더 이상 그 전 문자가 없으므로 찾으려는 문자를 한 칸 이동시킨다.

1. 2번 그림을 보면, 거의 모든 문자열이 같지만, 마지막 문자가 일치 하지 않다는 것을 확인한다.
2. 그 전 문자의 테이블이 2이니까, 2번 인덱스와 다시 확인 후, 불일치 확인, 그 전 문자의 테입블이 0이니까, 0번 인덱스와 확인후 불일치를 확인해서, 더 이상 그 전 문자가 없으므로, 찾으려는 문자를 한 칸 이동시킨다.
3. 모든 문자가 일치하는 것을 확인한다.

위와 같은 과정으로 KMP알고리즘이 동작된다고 알면 된다.