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

한빛미디어

뇌를 자극하는 알고리즘

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

Boyer-Moore 에서

2011-12-24

|

by lastcig

2257

4 쇄 p.454 에서

빈 접미부는 경계가 없으므로 이동 거리는 패턴의 길이(6) + 1 = 7  라고 하시고는 바로 다음줄에 또 이동 거리는 1.
표를 보면 접미부의 가장 넓은 경계의 시작 위치일 것 같은데요.
이 접미부의 가장 넓은 경계의 시작 위치 (접시 라고 할께요 너무 길어서) 라는게 뭘 뜻하는지 모르겠습니다.
왜 5 번째 A 에 해당하는 접시가 6 인지, 왜 4 번째 B 의 접시도 6 인지. 그림에 표시라도 해주세요.

그리고 설명에 따르면 아래의 경우

문자: ....KKAAXABAKKK....
패턴: ....AAXABA

접미부 A 에 대한 good suffix 이동거리가 4 이고 X 에대한 bad character 이동거리가 2 이므로 max 연산으로 4 만큼 shift 하면 target 을 지나쳐 버리게 되는데요.
이상합니다. 설명해 주세.
댓글 입력