As always in such cases, the answer is "introduce structure". In this case, you can abuse split. my @result = split /($query)/, $source; Then it's just a matter of keeping track of the previous element's tail's length while line-chopping them one after the other as you would do to the single element, and only finally adding highlights to the matches. Untested:

my ($extra, $tag_it) = (0, 0);
my $output = "";

for(@result) {
    my @line = split /\n/, $_, -1;
    unshift @line, unpack "A$extra A*", shift @line;
    @line = map split /(.{80})/, @lines;
    $extra = 80 - length @line[-1];
    $output .= $tag_it ? "<span>$_</span>" : $_
        for join "<br />\n", @line;
    $tag_it = not $tag_it;
}
[download]

Makeshifts last the longest.