KMP 표 건물 알고리즘

Question

은 내가 KMP table-building algorithm from Wikipedia을 확인하지만 난이 알고리즘을 사용하여 테이블을 만들려고 while 루프

(second case: it doesn't, but we can fall back) 
     else if cnd > 0 then 
      let cnd ← T[cnd] 

의 두 번째 경우 뒤에 논리를 이해하지 않고 완벽하게 작동합니다. cnd ← T[cnd]은 적절한 접미사 길이를 찾는 데 도움이됩니다. 내가 이해하지 못하는 것은 "어떻게"그것을 하는가?

예를 들어 설명하는 것이 좋습니다.

감사합니다.

편집 : "Partial match" table (aka "failure function") in KMP (on wikipedia)

내가 지금 답변을 얻을 생각 : 난 그냥 내 질문은 여기에 질문의 중복 된 것을 발견했다. 하지만 한 가지 더 설명하면 도움이 될 것입니다. 감사!

Answer 1

문자열이 Hello World!!!이고 Head Up을 검색한다고 가정합니다. 첫 번째와 두 번째 문자에있을 때

Hello World!!! 
Head Up 
^

첫 번째 조건이 표시된 위치의 경우, (first case: the substring continues)을 적용, 문자가 일치하지 않습니다하지만 당신은 하위 문자열 일치 (2 문자 내부에 이미 까지 일치),이 경우는 두 번째 조건 인 (second case: it doesn't, but we can fall back)에 해당합니다. 세 번째 경우는 패턴의 첫 번째 문자와 일치하지 않는 경우입니다.

두 번째 조건은 미스 매치 때까지 일치하는 문자의 정보를 사용할 수 있기 때문에 불필요한 비교를 피하기 위해 필요한 결과입니다 (이미 string의 문자는 건너 뜁니다. 패턴이 일치하지 않음).

예 : 문자열 패턴 HeHello World!!!HeHello위한 패턴 테이블을 구축하는 경우 Hello

HeHello World!!! 
Hello 
^when you miss match this character using the table of KMP you known that 
    could skip 2 characters because 

HeHello World!!! 
Hello 
^ this would miss match 

를 검색로. ^이 cnd이고 *이 pos이라고 가정합니다. 시작 포인트는 pos = 2 및 cnd = 0입니다 (패턴 체크인시 pos - 1 = 1 인 경우).

HeHeHello  T [-1,0,0,0,0,0,0,0,0] 
^* comparing 0 with 1 go to condition 3  cnd = 0, pos = 2 
         _ 
HeHeHello  T [-1,0,0,1,0,0,0,0,0] 
^ * comparing 0 with 2 go to condition 1  cnd = 0, pos = 3 
          _ 
HeHeHello  T [-1,0,0,1,2,0,0,0,0] 
^ * comparing 1 with 3 go to condition 1  cnd = 1, pos = 4 
          _ 
HeHeHello  T [-1,0,0,1,2,3,0,0,0] 
^* comparing 2 with 4 go to condition 1  cnd = 2, pos = 5 
           _ 
HeHeHello  T [-1,0,0,1,2,3,4,0,0] 
^* comparing 3 with 5 go to condition 1 cnd = 3, pos = 6 

HeHeHello  T [-1,0,0,1,2,3,4,0,0] 
    ^* comparing 4 with 6 go to condition 2 (cnd = T[cnd], cnd = T[4] = 2) 

HeHeHello  T [-1,0,0,1,2,3,4,0,0] 
^ * comparing 2 with 6 go to condition 2 (cnd = T[cnd], cnd = T[2] = 0) 

...