<보기>의 텍스트 문자열 T와 패턴 문자열 P에 대해 KMP… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
<보기>의 텍스트 문자열 T와 패턴 문자열 P에 대해 KMP(Knuth-Morris-Pratt) 알고리즘을 수행하여 인덱스 5에서 불일치(mismatch)가 발생하였다. 다음에 비교할 패턴 문자열 P의 인덱스로 가장 옳은 것은? (단, 패턴 문자열 P의 인덱스는 0부터 시작한다.)<보기>
0 1 2 3 4 5 6 7 8 9 10 T a b a b a d a a b c d = = = = = ≠ P a b a b a c
1
0
2
1
3
2
4
3
해설
다음에 비교할 패턴 인덱스는 3이다.
불일치 직전까지 일치한 P[0..4] = ababa에서 가장 긴 접두사이자 접미사는 aba로, 길이가 3이다.
따라서 T의 인덱스 5는 그대로 두고 패턴을 밀어 P[3]부터 비교를 이어 간다.
- 인덱스 0: 실패 함수를 쓰지 않고 패턴 처음부터 다시 비교하는 단순 매칭의 동작이다.
- 인덱스 1: 길이 1인 a만 고려한 값으로, 더 긴 aba를 놓친다.
- 인덱스 2: ab는 ababa의 접미사가 아니므로 경계가 될 수 없다.
오류나 개정된 내용이 보이면 알려주세요