From 56e59b92a9170f87083f3a6f6c9ba02092cbfbc1 Mon Sep 17 00:00:00 2001
From: Jesse Luehrs <doy@tozt.net>
Date: Sat, 17 Nov 2012 15:55:57 -0600
Subject: another solution

---
 LCSQ.pl | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)
 create mode 100644 LCSQ.pl

(limited to 'LCSQ.pl')

diff --git a/LCSQ.pl b/LCSQ.pl
new file mode 100644
index 0000000..e88564f
--- /dev/null
+++ b/LCSQ.pl
@@ -0,0 +1,29 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use 5.016;
+
+no warnings 'recursion';
+
+use Memoize;
+
+chomp(my $str1 = <>);
+chomp(my $str2 = <>);
+
+say lcsq($str1, $str2);
+
+sub lcsq {
+    my ($str1, $str2) = @_;
+
+    return '' unless length($str1) && length($str2);
+    if (substr($str1, 0, 1) eq substr($str2, 0, 1)) {
+        return substr($str1, 0, 1)
+             . lcsq(substr($str1, 1), substr($str2, 1));
+    }
+    else {
+        my $lcsq1 = lcsq(substr($str1, 1), $str2);
+        my $lcsq2 = lcsq($str1, substr($str2, 1));
+        return length($lcsq1) > length($lcsq2) ? $lcsq1 : $lcsq2;
+    }
+}
+BEGIN { memoize('lcsq') };
-- 
cgit v1.2.3-54-g00ecf