Yes, you can. There's an algorithm running in O((r+l) log l) time, where l is the number of lines and r is the total number of ordered pairs of line numbers at which the two files match [1]. So if all lines are unique, this runs in O(l log l).
[1] J. W. Hunt and T. G. Szymanski. A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5):350–353, 1977.
As the paper itself says, this is still N^2 log N worst case :)
Note that these are all variants of general algorithm I posted, and more generally, variants of tricks used in boyer-moore (though hunt's work predates boyer-moore, that's the easiest way to describe it), which means they try to skip parts of the text they can prove can't match.
Because they can't always do so, they don't change the worst case time bound, only various other time bounds.
[1] J. W. Hunt and T. G. Szymanski. A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5):350–353, 1977.