나는 Wikipedia article about the Knuth-Morris-Pratt algorithm을 읽었으며 점프/부분 일치 테이블에 값이 어떻게 표시되는지 혼란 스럽습니다.Knuth Morris Pratt (KMP) 오류 기능 이해
i | 0 1 2 3 4 5 6
W[i] | A B C D A B D
T[i] | -1 0 0 0 0 1 2
문장
은 "우리가 [2] 길이 2 W에 적절한 접두사와 결말을하는 적절한 접미사를 발견 가정 해 봅시다 때문에 사람이 더 명확 바로 가기 규칙을 설명 할 수있는 경우 (최대 가능) "
은 혼란 스럽습니다. 올바른 접미사가 W [2]에서 끝나면 3의 크기가되지 않습니까?
크기 1의 접두사와 접미사가있을 때 T [4] 1이 아닌 이유도 궁금 해요 다음 A. 제공 할 수있는 모든 도움을
감사합니다.
실패 함수 T [i]는 i를 인덱스로 사용하지 않고 길이로 사용한다는 점에 유의하십시오. 그러므로, T [2]는 문자의 끝나는 문자열에 의해 형성된 가장 긴 적절한 경계가 아니라 W의 처음 두 문자로 형성된 문자열의 가장 긴 적절한 경계 (길이가 접두사와 접미사 인 문자열)를 나타냅니다 이것이 T [2]의 가능한 최대 값이 3이 아니라 2 인 이유입니다. W의 처음 두 문자에서 형성된 부분 문자열은 2보다 큰 길이를 가질 수 없습니다.
이 해석을 사용하면 왜 T [4]가 1이 아닌 0인지 쉽게 알 수 있습니다. W의 처음 네 문자에서 형성된 W의 하위 문자열은 적절한 접미사 인 적절한 접두사가없는 ABCD입니다.
희망이 도움이됩니다.
가 좋아, 길이가 최대 2 일 수있다 "우리가 W에 적절한 접두사 및 종료 [2] 길이 2 (가능한 최대)로이다 적절한 접미사를 발견 가정 해 봅시다", 그것은 맞습니다 다음과 같은 이유가 있습니다 ... 하나의 사실 : "적절한"접두사는 전체 문자열이 될 수 없습니다. 적절한 접미사 (올바른 하위 집합과 동일)가 될 수 있습니다.
W [0] = AW [1] = AW [2] = A, 즉 패턴이 "AAA"이므로 (최대 길이) 적절한 접두사는 "AA"(왼쪽에서 오른쪽)이고 (최대 길이) 적절한 접미사는 "AA"일 수 있습니다 오른쪽에서 왼쪽) // 예, 접두사와 접미사에 겹침이 있습니다 (가운데 "A")
그래서 값은 3이 아니라 2가 될 것이며 접두어가 적절하지 않은 경우에만 3이됩니다.
많은 도움이되었습니다. 또한 바로 가기 규칙의 작동 방식을 명확히하는 데 도움이 될 수 있습니까? – Shaun
@ Shaun- "바로 가기 규칙"이란 무엇입니까? KMP에 익숙하지만 이전에는이 용어를 들어 보지 못했습니다. – templatetypedef
내 이해에서 그것은 T [i]의 이전 값을 사용하여 현재 값을 계산합니다. 나는 그것이 어떻게 이루어 졌는지 궁금해하고 있었다. – Shaun