lcs.pl

30分シリーズ。その8。なんか不調。
今回は最長共通部分列問題。http://mono.kmc.gr.jp/~oxy/acmicpc/hiki.cgi?%C6%B0%C5%AA%B7%D7%B2%E8%CB%A1あたりが参考になるかも。

要するに、2つの文字列を受け取って、その両方に登場する最長の文字列を取り出す問題。ただし、それぞれの文字列は前後関係だけを守っていれば良くて、連続である必要はない。

$ perl lcs.pl hoge hoge
hoge

$ perl lcs.pl xMZPy zMZPw
MZP

$ perl assault salty
salt

#!/usr/local/bin/env perl # -*- perl -*-
use strict;
use warnings;

sub lcs{
    my ($lhs,$rhs) = @_;
    return '' if $lhs eq '' or $rhs eq '';

    my $l_top = substr($lhs,0,1);
    my $l_rest=substr($lhs,1);

    my $r_top=substr($rhs,0,1);
    my $r_rest=substr($rhs,1);

    if($l_top eq $r_top){
	$l_top . lcs($l_rest,$r_rest);
    }else{
	my $x1 = lcs($l_rest,$rhs);
	my $x2 = lcs($lhs,$r_rest);
	length($x1) < length($x2) ? $x2 : $x1;
    }
}

$#ARGV < 2 or die;
print lcs($ARGV[0],$ARGV[1]),"\n"

• Perlで文字列は配列のように扱えない。単なるスカラー値。だから先頭一文字取り出すのにだいぶ苦労してる
• どうしても、文字列を=で比較してしまう。'.'(ドット)による連結はすんなりと納得できるのに