<보기>의 텍스트 문자열 T와 패턴 문자열 P에 대해 KMP… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
<보기>의 텍스트 문자열 T와 패턴 문자열 P에 대해 KMP(Knuth-Morris-Pratt) 알고리즘을 수행하여 인덱스 5에서 불일치(mismatch)가 발생하였다. 다음에 비교할 패턴 문자열 P의 인덱스로 가장 옳은 것은? (단, 패턴 문자열 P의 인덱스는 0부터 시작한다.)
<보기>
012345678910
Tababadaabcd
=====≠
Pababac
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의 접미사가 아니므로 경계가 될 수 없다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기