Practical KMP/BM style pattern-matching on indeterminate strings

We describe three algorithms for identifying matches of an indeterminate pattern in an indeterminate text, both encoded so that indeterminate entries of up to 9 letters can be accommodated in a single computer word. The two proposed algorithms, KMP-Indet and BM-Indet, extend well-known algorithms, Knuth–Morris–Pratt and Boyer–Moore. The third is a simple “brute force” algorithm (BF). All three algorithms are fully implemented. Recently, several other such algorithms have been proposed, including the DBWT algorithm (Daykin et al. 2019) with a (partial) implementation. We show that all our algorithms execute an order-of-magnitude faster than DBWT on randomly-generated strings over different alphabet sizes.