라빈－카프(Rabin-Karp) 알고리즘에 대한 설명으로 옳지 않은 것… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 23년 1회차

라빈－카프(Rabin-Karp) 알고리즘에 대한 설명으로 옳지 않은 것은? (단, 패턴 문자열의 길이는  $m$ , 대상 문자열의 길이는  $n$ ,  $m \le n$ 이다)

패턴 문자열에 대한 해시 값 1개, 대상 문자열에 대한 해시 값이 최대  $n-m+1$ 개 생성된다.

문자열의 해시 값을 계산하는 과정에서 호너의 방법(Horner’s rule)을 사용할 수 있다.

해시 값이 컴퓨터 레지스터의 용량을 초과할 경우, 나머지 연산 (mod)을 사용한다.

패턴 문자열의 해시 값과 대상 문자열의 일부 문자열에 대한 해시 값이 일치하면 알고리즘을 종료한다.

해설

해시 값이 같아도 문자열이 실제로 같다는 보장이 없으므로(해시 충돌), 해시 값이 일치하면 바로 종료한다는 설명이 옳지 않다.

해시 값이 일치하면 해당 위치의 문자를 하나씩 직접 비교해 실제 일치인지 확인하고, 모든 출현 위치를 찾을 때까지 다음 위치로 계속 진행한다.

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

이어서 풀어보기