I am looking for an algorithm to search a substring in a string. I know there are a number of wellknown Algorithms like Knuth-Morris-Pratt, for instance, and I suppose most preimplemented functions use one of those. However, I remember a lecture, long ago, where the lecturer said that the usefullness of such an algorithm depends partly on the size of the alphabet. KMP and BMH obviously work fine on an ordinary 26-letter alphabet. But what do I do if I have a much smaller alphabet (say, DNA: 4 letters or simply a binary)?

Are there an particular algorithms that work well on very small alphabets? I googled and supposed I should easily find something as searching through DNA is rather common, but to no avail. Any help?

Please do not downvote, this is my first question in this subcommunity, I do not know yet what is considered too basic here and what is ok.

  • $\begingroup$ If you have a small alphabet, like DNA, then for some small k, it's possible to enumerate all length-k substrings of the text string you are looking in. You can store the positions of each of the $4^k$ possible such substrings in an array of lists, and then read characters from your pattern string $k$ at a time, and simply look up the matching positions in this table. This kind of indexing is much faster than KMP et al. if (a) you will search for many different short substrings in the same text and (b) matches are rare. It can even be extended to approximate matching; Google e.g. BLAST. $\endgroup$ – j_random_hacker Mar 31 '16 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.