What you want is the unanchored version of String::Approx. In other words, what it does, except with zero cost for insertions at the start or end of the small sequence. The C code of S::A is a bit hairy, so modifying that might not be the best way. A google search for "local alignments" should turn up lots of good references -- bioinformatics is well-documented online if you know the right keywords.