KMP 알고리즘이란?
문자열 패턴 매칭에 사용되는 알고리즘이다
FAIL 함수를 사용해 패턴을 전처리한다
-> 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 FAIL 함수를 통해 매칭을 시킨다
- 시간복잡도 : O(M+N)
여기까지만 보고 이해가 되긴 어렵다..
그래서 실제 문제를 통해 FAIL 함수를 만들고 문자열 매칭을 해보자!
문제 예시 1
주어진 문자열
ABABABABCABABACA
찾고자 하는 문자열
ABABACA
1. 실패함수 FAIL 만들기
매칭이 실패했을 때 돌아갈 곳을 계산
0 ~ 해당 인덱스까지의 부분문자열 중 접두사&접미사가 일치하는 최대 길이로 계산
0위치는 돌아갈 곳이 없기 때문에 실패함수값은 0
j=0에 해당하는 접미사는 A -> 접미사 불일치 -> 최대길이 0 -> 실패함수값은 0
j=0에 해당하는 접미사는 A -> 접미사,접두사 공통으로 A 존재한다 -> 최대길이 1 -> 실패함수값은 1
j=1에 해당하는 접미사는 AB -> 접미사,접두사 공통으로 AB 존재한다 -> 최대길이 2 -> 실패함수값은 2
j=2에 해당하는 접미사는 ABA -> 접미사,접두사 공통으로 ABA 존재한다 -> 최대길이 3 -> 실패함수값은 3
j=3에 해당하는 접미사는 ABAB -> 접미사와 불일치
j=3에서 불일치 => j=2까지는 일치한다는 의미
fail(2)=1 이용해서 j=1로 위치 변경
j=1에 해당하는 접미사는 AB -> 접미사와 불일치
j=1에서 불일치 => j=0까지는 일치한다는 의미
fail(0)=0 이용해서 j=0으로 위치 변경
j=0에 해당하는 접미사는 A -> 접두사,접미사와 불일치 -> 실패함수값 0
j=0에 해당하는 접미사는 A -> 접미사,접두사 공통으로 A 존재한다 -> 최대길이 1 -> 실패함수값은 1
2. Fail 함수 사용해서 문자열 비교
j=0 ~ 4까지는 일치하므로 넘어간다
j=5에 해당하는 접미사는 ABABAC -> 접미사와 불일치
j=5에서 불일치 => j=4까지는 일치한다는 의미
fail(4)=3 이용해서 j=3으로 위치 변경
j=3부터 일치하므로 계속 진행
j=5에 해당하는 접미사는 ABABAC -> 접미사와 불일치
j=5에서 불일치 => j=4까지는 일치한다는 의미
fail(4)=3 이용해서 j=3으로 위치 변경
j=3부터 일치하므로 계속 진행
j=4에 해당하는 접미사는 ABABA -> 접미사와 불일치
j=4에서 불일치 => j=3까지는 일치한다는 의미
fail(3)=2 이용해서 j=2으로 위치 변경
j=2에 해당하는 접미사는 ABA -> 접미사와 불일치
j=2에서 불일치 => j=1까지는 일치한다는 의미
fail(1)=0 이용해서 j=0으로 위치 변경
j=0에 해당하는 접미사는 A -> 접미사와 불일치 -> 다음칸으로 넘어가기
이후에는 j 계속 증가하면서 모든 패턴이 일치하므로 패턴 매칭이 완료된다!
