#!/usr/bin/perl -p
s-^(((((((h?t)?)t)?p)?:)?/)?/)?(?=\w+\.)-http://-;
__END__
http://www.perlmonks.org/
ttp://www.perlmonks.org/
tp://www.perlmonks.org/
p://www.perlmonks.org/
://www.perlmonks.org/
//www.perlmonks.org/
/www.perlmonks.org/
www.perlmonks.org/
[download]

produces

http://www.perlmonks.org/
http://www.perlmonks.org/
http://www.perlmonks.org/
http://www.perlmonks.org/
http://www.perlmonks.org/
http://www.perlmonks.org/
http://www.perlmonks.org/
http://www.perlmonks.org/
[download]

(update:) Replace \. with [./] if you want to support intranet URLs like http://cvs/. Supporting alternate-port intranet URLs like http://wiki:8080/ with just [./:] would cause ftp://... to become http://ftp://... but you could consider (?=\w+([./]|:\d)).