Use Regexp::Approx - Use fuzzy regular expressions. It uses String::Approx internally to do the approximate matching but avoids the problem of the regexp engine not being re-entrant (which is the problem you run into if you use String::Approx directly from within your regexp).