あらゆる場所を検索しましたが、カンガルー法に関する適切で明確な説明は見つかりませんでした。私が見つけたのはいくつかの ppts だけでしたが、カンガルー法を読んだことがないので役に立ちませんでした。
誰かがカンガルー法に関する読み物やビデオチュートリアルのリンクを私に提供してくれれば、それは大きな助けになります.
事前に感謝
質問する
730 次
1 に答える
4
T = t1t2 ... tn、P = p1p2...pmとします
k =＃許容されるエラー
T $ 1P $ 2の接尾辞木を前処理します[時間：O（nlog | Sigma | by Weinerアルゴリズムによる接尾辞木を構築します）Sigmaは言語です。
作成したツリーでLCAを前処理します。[時間：O（n）]
すべてのノードで実行し、ルートからの高さを各ノードに書き込みます。[時間：O（n）ノードがあります]
すべての接尾辞（= Leaves）を繰り返し、各接尾辞Siに対してerrカウンターを初期化し、h1 = height（LCA（Si、P））を照会します。h> = mの場合、ソリューションにiを追加します。それ以外の場合、err++およびif err<=kはh2=height（LCA（Si [h1 + 1、n]、P [h1 + 1、m]））のチェックを続けます。
[時間：すべてのサフィックスで実行=> O（n）、各サフィックスでk +1回まで実行=>O（kn）]
これがお役に立てば幸いです...
ブッシュ
于 2012-08-26T14:16:02.027 に答える