21st EANN 2020, 5 -7 June 2020, Greece

Detecting Pattern Efficiently with Don’t Cares

Hayam Alamro, Costas Iliopoulos


  In this paper, we introduce our efficient simple method which can locate all occurrences of pattern P of k subpatterns with "don't cares" of length m in text S of length n. Our algorithm employs advanced data structure and the Kangaroo method, which can be applied to selected suffixes of the suffix tree of S to answer subsequent queries in O(k) time using a predefined computational method to find all occurrences of pattern P with "don't cares" in text S in a fast and effective manner.  

*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.