Longest repeats with a block of k don't cares
A k-repeat is a string w(k) = u* (k)v that matches more than one substring of x, where is the don't care letter and k > 0. We propose an O(n log n)-time algorithm for computing all longest k-repeats in a given string x = x[l..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. (C) 2006 Elsevier B.V. All rights reserved.
repeat don't care string combinatorial pattern matching