String searching

String searching with don't cares

In this version of the string searching problem, there is a special symbol, ø (read: don't care), which can match any other symbol (including another ø). Don't care symbols can appear either in the pattern or in the text. In 2002, an algorithm for this problem that runs in ${\displaystyle O(n\log m)}$ time has been given by Richard Cole and Ramesh Hariharan, improving on a solution from 1973 by Fischer and Paterson that has complexity ${\displaystyle O(n\log m\log k)}$, where k is the size of the alphabet. Another algorithm, claimed simpler, has been proposed by Clifford and Clifford.