Longest repeats with a block of k don’t cares

A k-repeat is a string wk=u*kv that matches more than one substring of x, where * is the don’t care letter and k>0. We propose an -time algorithm for computing all longest k-repeats in a given string x=x[1..n]. The proposed algorithm uses suffix trees to fulfill this task and relies on the ability to answer lowest common ancestor queries in constant time.