Pseudo-realtime Pattern Matching: Closing the GapRaphaël Clifford, Benjamin Sach, Pseudo-realtime Pattern Matching: Closing the Gap. Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 101–111. June 2010. PDF, 161 Kbytes.
We consider the k-difference and k-mismatch problems in the pseudo-realtime model where the text arrives online and the time complexity measure is per arriving character and unamortised. The well-known k-difference/k-mismatch problems are those of finding all alignments of a pattern of length m with a text of length n where the edit/Hamming distance is at most k. Offline, the literature gives efficient solutions in O(nk) and O(n sqrt(k log k)) time, respectively. More recently, a pseudo-realtime solution was given for the former in O(k log m) time and the latter in O(sqrt(k log k)log m) time per arriving text character. Our work improves these complexities to O(k) time for the k-difference problem and O(sqrt(k) log k + log m) for the k-mismatch problem. In the process of developing the main results, we also give a simple solution with optimal time complexity for performing longest common extension queries in the same pseudo-realtime setting which may be of independent interest.