Well searching/counting/etc k-mers can be done with regexps, but I certainly agree that regexp-based searching is somewhat niche compared to more generally usef

Well searching/counting/etc k-mers can be done with regexps, but I certainly agree that regexp-based searching is somewhat niche compared to more generally useful similarity searches like BLAST. One comment though: backtracking is not inherently an issue with regexps. Some implementations will never backtrack, and others that do (like perl's) are nowadays pretty good at avoiding the exponential worst-cases that I think you're referring to, for all but the most pathological cases.