KMP는 대표적인 문자열 매칭 알고리즘으로, 문자열과 패턴이 주어질 때 문자열 안에서 주어진 패턴을 찾아내는 알고리즘이다. 만약, 길이가 1,000,000인 문자열과 길이가 10,000인 패턴이 주어졌을 때 단순하게 모든 문자열의 경우의 수를 확인한다면 시간 복잡도는 접두사, 접미사 최대 개수를 담은 table 생성앞서 말한 과정에서 미리 계산해 둔 접두사, 접미사 정보를 활용한다고 나온다. 이에 해당하는 정보는 패턴의 패턴이 이에 대한 정보를 리스트에 저장을 해주어야한다. 이를 만드는 알고리즘은 다음과 같다.
만약, 5에 저장한다. 이후 i 를 증가시킨다.여기서는 이후부터는
KMP 함수 작성최대 일치하는 접두사와 접미사를 구했다면 이제 이를 활용하여 KMP 알고리즘을 완성시켜야한다. 우선 크게 이제 문제는 문자열의 위의 예시를 보면 위의 예에서는 아래는 KMP 알고리즘의 전체 코드이다.
정리하며...이번 글에서는 문자열 매칭 알고리즘인 KMP 알고리즘에 대하여 알아보았습니다. 처음 KMP 알고리즘이라는 이름을 보고 아주 이해하기 어려울줄만 알았지만, 직접 예제를 그림으로 과정을 그려보며 알고리즘을 공부해보니 생각보다는 쉽게 이해를 했던 것 같습니다. 해당 글이 설명이 부족할 수도 있지만 이 알고리즘을 검색해서 찾아보았다면 충분히 코드를 읽어보고 차근차근 예제를 그림으로 직접 그려본다면 쉽게 이해할 수 있을거라고 예상합니다. 부족한 글 읽어주신 점 감사드립니다^^ |