0

我有两个字符串。

它们不是彼此的子串，但它们之间存在重叠区域。

my $str1 = "AAAAAAAAAABBBBBBBBCC";
my $str2 = "BBBBBBBBCCZZZZZZZZZZ";

我想找到这个重叠区域。

 "AAAAAAAAAABBBBBBBBCC"
           "BBBBBBBBCCZZZZZZZZZZ"

Overlap is "BBBBBBBBCC"

我广泛搜索了 CPAN 和谷歌。

有很多关于“编辑距离”方法的模块，例如Algorithm::Diff，Text::Levenshtein或Text::OverlapFinder和String::Similarity。但是，它们不是我想要的。

字符串不应间隔（插入或删除任何字符）或替换。它类似于生物信息学中的序列比对，但没有间隙“开放”和“扩展”许可，除非在两个极端情况下。

我想知道是否有人找到了解决方案或解决方法。

4

2 回答 2

4

检查String::LCSS_XS模块，

use String::LCSS_XS 'lcss';

my ($s1,$s2) = qw(
  AAAAAAAAAABBBBBBBBBB
  BBBBBBBBBBCCCCCCCCCC
);
my $longest = lcss ($s1, $s2);
print "$longest\n";

输出

BBBBBBBBBB
于 2014-06-06T14:08:30.850 回答
1

因为您正在寻找有界重叠，所以这是一个足够简单的问题，蛮力是要走的路。使字符串长度相等，然后只删除字符，直到找到匹配项。

有一些潜在的途径可以提高效率，但只有在这变得太慢时才探索这些途径。

use strict;
use warnings;

sub overlap {
    my ($str1, $str2) = @_;

    # Equalize Lengths
    if (length $str1 < length $str2) {
        $str2 = substr $str2, 0, length($str1);
    } elsif (length $str1 > length $str2) {
        $str1 = substr $str1, length($str1) - length($str2);
    }

    # Reduce until match found
    while ($str1 ne $str2) {
        substr $str1, 0, 1, '';
        chop $str2;
    }

    return $str1;
}

while (<DATA>) {
    print "Overlap is " . overlap(split), "\n";

}

__DATA__
AAAAAAAAAABBBBBBBBBB  BBBBBBBBBBCCCCCCCCCC
aln.trp.leu.tre       leu.tre.met.ile
aaaaaaaaaaaaaaaaaaaZ  aaaaaaaaaaaaaaa

输出：

Overlap is BBBBBBBBBB
Overlap is leu.tre
Overlap is
于 2014-06-06T16:27:28.533 回答