KMP 알고리즘 완벽 정리
KMP 알고리즘이 어떻게 되는 지 찾다 보면 여러 블로그에서 어떻게 되는 지 설명해 주기는 하는 데, 조금씩 다 달라서 오히려 헷갈리더라. 그래서. 오늘은 헷갈리는 부분에 대한 KMP알고리즘의 전체적인 정리를 해보려고 한다. KMP알고리즘이란 KMP알고리즘이란 쉽게 말해 일일이 확인하던 문자열 string의 불필요한 탐색 시간을 좀 더 효율적으로 줄이기 위해 나타난 방법이다. 예를 들어 ababcaba 라는 문자열이 있다고 치자. ababcaba 문자열 테이블 만들기 이 문자열의 반복되는 정도를 확인하기 위해 테이블을 만든 다. 이 블로그 하나로 이해가 되길 바란다. 테이블이 만들어 지는 조건은 다음과 같다. 접두사(i)와 접미사(j)가 같다면 숫자가 1올라간다. 그 전 접두사와 접미사가 일치 후, 그 다음 찾으려는 문자가 일치하지 않다면, (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번을 보면, 6번째 인덱스에서 일치하지 않는 것이 확인되면,...