메뉴 바로가기 검색 및 카테고리 바로가기

한빛미디어

뇌를 자극하는 알고리즘

뇌를 자극하는 알고리즘 질의응답 게시판입니다.

kmp 알고리즘에서 나오는 경계에 대해 질문 드립니다.

2012-10-08

|

by ban007

3266

4쇄 발행 443p, 444p 에 나오는 표를 보면
일치접두부의 길이가 6,7인 부분의 일치 접두부의 최대경계너비가 둘다 0으로 되어 있는데
일치접두부의 길이가 6인 부분의 일치접두부의 최대경계너비는
최대 경계가 B가 되므로 1이어야 하고,
일치접두부의 길이가 7인 부분의 일치접두부의 최대경계너비는
최대 경계가 BA이므로 2이어야 하지 않을까 생각됩니다.
확인 부탁드립니다~

또, kmp알고리즘에 대해 웹사이트를 검색하다 보니
http://carstart.tistory.com/m/post/view/id/143
이분의 사이트에서 kmp 알고리즘에 대한 설명을 보게되었는데요.
이분의 설명으로는 BAABABAA 이 문자열에서

"BAA     BA     BAA  
접두부와 접미부가 같은 BAA이다.
여기서 가운데 BA를 볼수가 있다.  
이 BA를 접두부와 접미부의 경계라 한다."

이렇게 설명을 해두셨었습니다.
책에 나온 설명과 완전 다른 설명인데요...
경계의 개념이 다르고, 문자열을 탐색해나가는 방식도 약간 달랐습니다.
저분의 설명대로 달리 이해한뒤, 문자열 탐색을 진행해도 같은 결과가 나오기도 하고,
경계의 개념이 다르면 보이어-무어 알고리즘에서도 달리 이해를 해야 하는 거라...
어떤게 맞는건지 혼란스럽습니다.

처음 제가 경계를 이해할때 경계라는 단어가 보통 "어떤 대상과 대상을 분간하는 사이"를 뜻하는 거라
서로 일치하는 접두부와 접미부 라는 저자님의 설명이 이해하기가 약간 어려웠었는데요...
혹시 저자님께서 독자들의 이해를 돕고자 단어가 뜻하는것과는 달리 경계를 정의하신뒤 설명하신것이 아닌지요...?

답변을 부탁드립니다.
댓글 입력