It runs forever because you have a loop while (1){ ... } in your testing code.

The runtime of the subroutine isn't that big.

Update:

Change the testing part at the bottom to read:

my $a = "abbacbacccabbacbacccccccccccgcccc";
my $b = "aabaabcbavcvcbvbvnbmhgfdgf";
print "LCS: ", lcs($a, $b), "\n\n";
[download]

Run time:

real    0m0.043s
user    0m0.039s
sys     0m0.002s
[download]