I see no reason to avoid the obvious tool: grep.

$ grep -F -f file2 file1 > outputfile
[download]

This should construct your first output file and likely do it faster than perl (benchmarking left as an exercise). If you can come up with an algorithm for your second output file then we can look at that in more detail.