Perlで任意の文字列同士を比較、共通項の有無を確認したい。

質問

Perlの勉強中です。任意の２つの文字列を比較して部分的に共通する部分があるか判断したいのですがそんな方関数はありますか？
例えば「yakiniku」と「ikayakisoba」ですと「yaki」がもっとも長い共通部分として返してほしいわけです。
両者ともその都度不特定の「任意の」文字列といったところがポイントです。一方が特定の文字列なら簡単なのでしょうが・・・
お詳しい方よろしくお願いいたします。
m(_"_)m

回答No.1

taseki · ベストアンサー

いまいち自信ないですが…。

まず以下のように考えてみました。

含まれていない文字、たとえばタブ文字は含まれていない前提とします（ヌルなどでも良いかも）。
で、それを区切り文字として2つをつなげてます。
そして最長マッチの法則を利用して、

$match = ("$text1\t$text2" =~ /[^\t]*?([^\t]+)[^\t]*?\t.*?\1.*?/) ? $1 : '';

でやってみると、一見うまくいったように見えましたが、よく考えたら左から探していってマッチしてしまった時点で、それ以上長い文字を探すことをやめてしまう、ということに気付きました。
たとえば「unadon」と「tendon」だと、「don」ではなく「n」でマッチしてしまいます。

で、結局ループを使って文字長から順に最長マッチを探す方法しか思いつきませんでした…。
それを関数として定義すると、以下のような感じです。

$text1 = 'yakiniku';
$text2 = 'ikayakisoba';
$match = &text_match($text1, $text2);
print $match;

# ---------------------------------
sub text_match {
my ($text1, $text2) = @_;
my $len = (length($text1) > length($text2)) ? length($text1) : length($text2);
my $match;
for (1; $len > 0; $len--) {
if ("$text1\t$text2" =~ /[^\t]*?([^\t]{$len})[^\t]*?\t.*?\1.*?/) { $match = $1; last;}
}
return $match;
}

お礼

なるほど！がっちり動きますね。
初心者なので一部意味がわかりませんでしたが、使えそうです。しかしやっぱり用意された関数はないのですね？
ありがとうございました。

回答No.2

bender

すでに簡潔な回答が寄せられているのですが、この問題は「最長共通文字列」を探す問題と似ているので、以下のような方法が効率がよいと思いました。

まず問題としては、文字列１の i 番目の文字と文字列２の j 番目の文字からそれぞれ始めて、共通する最長の文字列が何文字になるかを確認して、そのような共通文字列の中で最も長いものを返すような i, j の組み合わせを、すべての可能なi, j の組み合わせの中から探す、ということだと思います。
i, j についていえば、文字列１と２を含む Perl 変数をそれぞれ $s1, $s2 とすると、その範囲はそれぞれ 1<= i <= length($s1)、1<= j <= length($s2) になります。

ところで、ある i, j の組み合わせについては最長文字列の長さが仮に k と分かっているとき、組み合わせi-1, j-1から始まる最長文字列の長さは、文字列１の(i-1)番目と文字列２の(j-1)番目の文字が同じであれば k+1、そうでなければ 0 とすぐにわかるので、実は、このようにすでにわかっている情報を用いることで length($s1) * length($s2) 回の確認でこの作業をすませることができることになります。

ということで、以下のような手続きを書いてみました。

($text1, $text2) = ("oomori-yakiniku","niku-yakisoba");
print &text_match($text1,$text2);

sub text_match {
@s1=split(//,$_[0]);
@s2=split(//,$_[1]);
$match=””;
foreach $i (reverse (0..$#s1)) {
foreach $j (reverse (0..$#s2)) {
if($s1[$i] eq $s2[$j]) {
$c{join(",",($i,$j))}=$c{join(",",($i+1,$j+1))}+1;
$match=join("",@s1[$i..($i+$c{join(",",($i,$j))}-1)])
if($c{join(",",($i,$j))}>length($match));
}
}
}
return $match;
}

お礼

詳細な回答ありがとうございました。
試してみます！