3

I searched everywhere but didn't find a good, clear explanation on Kangaroo method. Only that I found was some ppts but were useless to me as I have not read kangaroo method before.Those ppts were for revision of the kangaroo method.

Please if anybody can provide me a reading material on kangaroo method or a video tutorial link, it will be a great help.

thanx in advance

1 Answer 1

4

Let T=t1t2...tn, P=p1p2...pm

k=# errors permitted

Preprocess a suffix tree for T$1P$2 [Time: O(nlog|Sigma| by Weiner algorithm to construct a suffix tree) Sigma is the language.

Preprocess an LCA on the tree we just created. [Time: O(n)]

Run on all nodes and write on each node it's height from the root. [Time: we have O(n) nodes]

Iterate over all the suffixes(=leaves) and for each suffix Si initialize an err counter and query the h1=height(LCA(Si,P)), if h>=m we add i to the solution, else: err++ and if err<=k continue to check h2=height(LCA(Si[h1+1,n],P[h1+1,m])).

[Time: running over all suffixes => O(n), for each suffix running up to k+1 times => O(kn)]

Hope this is helping...

Bush

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.