우리는 왜 이렇게 변하지 않습니까?

하는 문자열을 크 누스 - 모리스 - 프랫 알고리즘을 공부하는 동안 :우리는 왜 이렇게 변하지 않습니까?

ABC ABCDAB ABCDAB

을 패턴에 대한 :

ABCDABD

내가 한 단계에 붙어있다. 나는 현재 붙어있는 단계를 강조 할 것이다.

ABC ABCDAB ABCDAB 
ABCDABD 

ABC ABCDAB ABCDAB 
    ABCDABD 

ABC ABCDAB ABCDAB 
    ABCDABD 

ABC ABCDAB ABCDAB 
     ABCDABD--------------------(WHY THIS ?)

나는 위의 단계를 이해하지 못합니다. 위의 단계가 다음과 같을 것으로 기대합니다.

'올바른'단계의 논리/이유를 설명하십시오.

출처

2012-11-01 saplingPro

패턴의 두 번째 AB가 일치하므로 첫 번째 AB가 이제 두 번째 AB와 같도록 이동합니다. 왜 우리가 더 멀리 이동할 수 있다고 생각하니? –

@ n.m. _knuth morris_ algo와 함께 일하는 동안 찾아 볼 기준을 말해 줄 수 있습니까? 나는 완전히 [wikipedia article] (http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm)을 읽으려고했지만 완전히 이해하지 못한다. – saplingPro

''와 ''비교하면 불일치가 있습니다. 그리고이 알고리즘은 이전의 "AB"가 비교된다는 것을 '기억'하기 때문에 일치하지 않는 문자가 'C'인지 확인해야합니다.

KMP 방법에 대한 아이디어는 'Introduction to Algorithms'에서 설명합니다. 이는 무한 상태 시스템 방법과 매우 유사하며 이해하기 쉽습니다.

출처

2012-11-02 04:12:58 Richard

우리는 왜 이렇게 변하지 않습니까?

답변

관련 문제