패턴 : 찾고자 하는 문자열
텍스트 : 패턴을 찾을 문자열
교재 424p
KMP 알고리즘
텍스트의 위치 i에서 패턴의 j개 문자가 일치되었다고 하자
텍스트의 위치를 i->i+1로 증가
패턴의 j+1번째 문자와 비교
같으면 i,j 증가
같지 않다면 패턴에서 j개의 문자가 텍스트의 i 위치에서 일치되었으나 위치 i+1에서 j+1개의 문자는 일치하지 않았다
따라서 i+1에서 j+1개의 문자는 일치하지 않음
따라서 텍스의 i+1 위치에서 실제로 몇개의 문자가 일치되었는지 알아내야함
- i : 텍스트를 가리키는
- j : 클라이언트를 가리키는
i와 j 원소가 일치하지 않으면 i만 증가
일치하면 i와 j 같이증가
일치하다가 실패하면 j를 무슨 값으로 데려가야 하는가?
- 데려갔다 치고 다시 i와 j 증가하며 비교
- 다 매칭되면 매칭 위치 : i-j+1
KMP 는 패턴을 텍스트와 문자 하나씩 일치시켜 본다.
문자를 하나씩 이동하다가 불일치가 나오면 모든 것을 버리고 패턴의 처음 문자부터 시작한다. 대신 가능하면 한 패턴에서 이미 매치된 부분을ㄹ 저장하려 한다.
불일치가 생길 때 패턴의 어느 부분을 재사용할 지 결정하는 방법을 알아야 함
- 접두사, 접미사
- 적절한 접두사, 접미사 (전체가 아닌것)
- 가장자리 : 한 문장에서 접두사이면서 접미사인 것
- 최대 가장자리 : 가장 긴 가장자리
ex ) ABAXYZABA의 최대 가장자리 : ABA
429p내용
-
불일치가 발생할 때 패턴에서 일치된 부분이 가장자리이면 이 패턴 부분을 재사용 할 수 있다.
-
꼭 가장자리랑 일치할 필요는 없지만 시도해봐야 한다
-
최대 가장자리인지
-
잠재적인 일치를 놓치지 않도록 내림차순으로 더 작은 가장자리를 살펴봐야 한다.
-
가장자리가 길수록 이동이 적어진다
-
최대 가장자리에서 시작해서 일치하는 부분을 건너띄지 않도록 가장자리를 줄여나가면서 확인해보아야 한다.
예시)
텍스트 : AABAABAAAA
패턴 : AABAAA
| A | A | B | A | A | B | A | A | A | A |
| A | A | B | A | A | A |
불일치발생
패턴에서 텍스트와 일치하는 접두사 : AABAA
최대 가장자리 : AA
다른 가장자리 : A
AA를 선택하고 오른쪽으로 3칸 이동해서 일치하게 된다
| A | A | B | A | A | B | A | A | A | A |
| A | A | B | A | A | A |
만약 최대 가장자리가 아닌 A를 선택하면 4칸 이동하게 된다
최대 가장자리 일 경우는 찾았을 일치를 못찾게 된다.
- 가장자리 배열
j 0 1 2 3 4 5 6 7 8 9 10 A B C A B C A C A B b[j] 0 0 0 0 1 2 3 4 0 1 2
패턴 ABCABCACAB에 대해 j에 따른 최대 가장자리의 길이를 b[j]에 기록한다
예를 들어 j=4이면 A가 최대 가장자리이므로 b[j]=1
j=7이면 ABCABCA에서 ABCA가 최대 가장자리이므로 b[j]=4
(접두사랑 접미사 겹쳐도됨)
