devbelly   6달 전

문자열 H에서 문자열 N을 찾는다고 가정하겠습니다.

이해가 되지 않는 부분은 

preview

   [사진1]

위 내용처럼 일치가 발생했을때 불일치와 똑같이 행동한다는 부분입니다.

preview

[사진2]

위 사진은 종만북에서 KMP 알고리즘의 일부를 발췌한것입니다 .

matched(현재까지 일치한 문자의 갯수)가 m(문자열N의 길이)이 될때 사진1에서 언급한것처럼 답에 추가를 하고

이후에 다시 while로 돌아와서 첫번쨰 if가 실패하므로(matched<m 이 성립안됨) 결국 else가 실행이 되는데

완벽하게 일치했을때 실패함수의 결과를 나타내는 pi배열의 값은 0이므로

시작부분이 matched 만큼 옮겨지게됩니다.

**질문** 왜 완벽하게 일치했을때 begin을  matched만큼 건너뛰어도 되는것인가요?

preview

1번 동그라미는 완벽하게 일치했을때

2번 동그라미는 완벽하게 일치 한 후 MATCHED만큼 스킵(제가 이해한게 맞다면)

3번동그라미도 답의 후보가 될 수 있는거 아닌가요? MATCHED만큼 스킵하면 3번은 답에서 제외되는것 아닌가요?

제가 무엇을 이해 못하고 있는지 잘 모르겠습니다. 너무 혼란스럽습니다

[++추가]

preview

clrmt   6달 전

끝까지 일치하면 완전히 점프하는게 아니라 다시 그 지점의 pi위치로 돌아갑니다. 일치하지 않았을 때랑 전부 일치했을 때랑은 원리가 같습니다. 어쨌든 지금까지 일부 일치했으므로 그 정보를 가지고 다음 시작위치를 찾습니다.

찾을 문자열 1 1 2 1 1 2 1 1 에서 끝까지 일치하면 1 1 2 1 1이 앞끝에서도 뒤끝에서도 등장하는 가장 긴 문자열이므로 1 1 2 1 1까지 일치했다고 보고 다음 2부터 검색을 계속합니다.

devbelly   6달 전

@clrmt
형님 설명은 모두 일치했을때 해당 pi[]가 0이 아니라는 말씀이신가요??

hwa3060   6달 전

저상황(N이 aabaabac)에서 완벽하게 일치했을때 pi 값은 0 이 맞지만 N이 aabaa 라고 가정했을때 완벽하게 일치했을때의 pi값은 2가 됨 그래서 끝까지 일치하면 완전히 점프하는게 아니라 pi 값을 보고 그만큼만 점프 하는거임

devbelly   6달 전

@hwa3060

아 이해했습니다 저는 모두 일치했을때 pi가 무조건 0이 되는줄 알았어요.. 감사합니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.