Socowi Socowi - 24 days ago 4
Perl Question

Perl module to check whether a string was created by inserting text into another string

Problem



I have two strings
$base
and
$succ
and want to check whether
$succ
can be created from
$base
by inserting arbitrary strings at arbitrary positions.

Some examples, written as isSucc(
$base
,
$succ
):


  • isSucc("abc", "abcX") is true, since we can insert X at the end of abc.

  • isSucc("abc", "XabYcZ") is true, since we can insert XaYbZ.

  • isSucc("abc", "abX") is false, since c was deleted.

  • isSucc("abc", "cab") is false, since c (the one at the end of abc) was deleted.

  • isSucc("abc", "cabc") is true, since we can insert c at the beginning of abc.

  • isSucc("", "anything") is true, since we just have to insert "anything".



We can assume, that
$base
and
$succ
do not contain any (vertical) withespace. Usually we have
length($base) < length($length) < 1000
. Good performance is not critical but would be nice to have.

I already know one way to implement
isSucc
*.

Question




  • Is there a perl-module that defines something similar to
    isSucc
    ?

  • Does someone has an easier/faster/alternative implementation* of
    isSucc
    ?



* My Approach



Compute the edit/Levenshtein distance with a custom cost model (cost(Insertion)=0, cost(Deletion)=cost(substitution)=1). Then check whether the edit distance is 0.

Answer
sub isSucc {
    my ($base, $succ) = @_;
    my $si = -1;
    for my $c (split //, $base) {     # for each character $c in $base
        $si = index $succ, $c, $si+1; # find it after the previous one in $succ
        return 0 if -1 == $si;        # return false if we can't
    }
    return 1;                         # return true if we found all the characters in $base inside $succ
}