One way to do it is by allocating string of length:

newlen = (strlen(str) * strlen("</p><p>")) / strlen("\r\n")
       + strlen("</p><p>") + 1;
[download]

which is in this case 3.5 times the length of the original string. This is the total number of bytes required in the worst case scenario: $str =~ /(\r\n)*/. Excessive memory can be reclaimed by doing a realloc *after* the substitution.

As for perl's internal implementation, it's a different issue as the regex engine must work with any regex given. But even with that in mind, you can still build a linked list of offsets and lengths of parts in the original strings that need to copied over, as well as another list of substitutions. The required amount of memory should be easy to compute and will require doing a single copy only.

For this example, this is like doing:

my $str = 'line1\r\nline2\r\n";
my $result = join '</p><p>', split(/\r\n/, $str);
[download]