입력으로 길이 의 텍스트 문자열(T)과 길이 의 패턴 문자열(P)이 있을 때, 문자열 매칭(string matching) 알고리즘에 대한 설명으로 옳지 않은 것은?
- ①브루트－포스(brute-force) 방식의 수행 시간은 이다.
- ②라빈－카프(Rabin-Karp) 알고리즘은 P의 해시(hash) 값을 이용한다.
- ③보이어－무어(Boyer-Moore) 알고리즘은 P의 각 문자를 왼쪽에서 오른쪽으로 스캔하면서 T와 비교한다.
- ④KMP(Knuth-Morris-Pratt) 알고리즘은 P의 각 문자에 대해 매칭 실패 시 비교를 다시 시작할 위치를 계산해 놓는다.
정답 ③
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)