나는 이것에 관한 대부분의 문헌을 읽으려고 시도했지만, KMP 알고리즘에서 사용 된 실패 함수가 어떻게 구성되는지 아직 이해하지 못했습니다. 대부분 사람들이 우수하다고 생각하는 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching 튜토리얼을 주로 언급했습니다. 그러나, 나는 아직도 그것을 이해하지 못했다. 나를 이해하는 데 더 쉽고 이해하기 쉬운 통증을 느낄 수 있다면 감사 할 것입니다.KMP 알고리즘에 사용 된 실패 함수는 어떻게 작동합니까?
실패 함수는 실제로 우리에게 이것을 알려줍니다. 문자열의 X 문자와 일치하는 경우 해당 문자열의 가장 긴 접미사는 검색 문자열의 접두사이기도합니다.
작성 방법을 묻는다면 접근 방법은 간단합니다.
문자열 끝에 새 문자를 추가하면 f [x]가 생성되고 f [x-1] 위치의 문자와 일치하면 f [x]는 f [x-1] +1.
다른 경우에는 일치하지 않는 경우 더 작은 접미어와 더 작은 접미어를 찾고 일치하는지 확인하십시오.
예를 들어 오류 기능을 구축하려는 단어가 "accadaccac"이고 문자를 'c'으로 추가했습니다. 마지막 문자 인 실패 문자를 작성하려고한다고 가정 해 봅시다. 문자는 'c'입니다.
"acca"와 접미사 "acca" 일치 할 수 있기 때문에 이전 편지의 실패 기능, 그 실패의 기능은 4이었다 확인하고 이제 문자 'c'를 추가, 그것은 문자 'd'과 일치하지 않습니다 후속 프리픽스 "acca"."acca"의 접미사는 이제 접두사 "accadaccac"이지만 "acca"보다 작습니다. 이 질문에 대한 대답은 길이가 1 인 접미사 (단지 문자 'a')가 a의 접두어이기 때문에 f [length ("acca") - 1] 또는 f [3] = 1 인 f [3] 검색 문자열.'c'이 1의 위치에있는 문자와 일치하면 시도해 볼 수 있습니다. 그러면 f [9] = f [f [8] -1] +1 = 2를 알 수 있습니다.이 정보가 도움이되기를 바랍니다. 행운을 빕니다! :)
http://www.oneous.com/Tutorial-Content.php?id=24
U는 KMP 알고리즘과 실패의 기능을 이해하기위한이 웹 사이트에서 학습 자원을 이용할 수있다. 또한 코드를 가져 와서 손으로 예제 문자열을 실행 해보십시오. 그러나 작업을 이해하는 가장 좋은 방법은 기본 알고리즘의 변형에 따라 코드를 작성하는 것입니다. 나는 NHAY부터 SPOJ에 시작하는 것이 좋습니다.
"접미사"acca "에 이어지는 접미사 'a'와 일치하지 않습니다." "accad"이기 때문에 문자 'd'를 의미합니까? – Tito