나는 캥거루 방법에 대해 도처에서 수사했지만 명확하고 명확한 설명을 찾지 못했습니다. 내가 찾은 것만이 일부 ppt 였지만 이전에는 캥거루 방법을 읽지 않아서 쓸모가 없었습니다.이 ppt는 캥거루 방법의 개정을위한 것이 었습니다.atm K 일치하지 않는 패턴 일치에 대한 캥거루 방법 허용
누군가가 나에게 캥거루 방법이나 비디오 자습서 링크에 대한 자료를 제공 할 수 있다면 큰 도움이 될 것입니다. 사전에
는고맙습니다
보자 T = T1T2 ... TN, P = P1P2 ... 오후
K = # 오류가
미리 처리 T에 대한 접미사 트리를 허용 $ 1P $ 2 [Time : O (nlog | Sigma | 접미사 트리를 구성하는 Weiner 알고리즘으로) 시그마는 언어입니다.
방금 만든 트리의 LCA를 사전 처리합니다. [시간 : O (n)]
모든 노드에서 실행하고 각 노드에 루트에서 높이를 씁니다. [시간 : 우리는 노드가있다]
모든 접미어 (= 잎)에 대해 반복하고 각 접미어 Si에 대해 err 카운터를 초기화하고 h1 = 높이 (LCA (Si, P))를 쿼리한다. > = m 우리는 용액에 i를 더한다. 그렇지 않다면 : err ++ 그리고 err이 거짓이면 < = k h2 = 높이 (LCA (Si [h1 + 1, n], P [h1 + 1, m]))를 계속 확인한다.
:이 돕는 [시간까지 실행 각각 접미사 모든 접미사 => O (N)를 통해 실행하는 단계는 k + 1 시간 => O (KN)]
희망 ...
부시