I have two strings
and want to check whether
can be created from
by inserting arbitrary strings at arbitrary positions.
Some examples, written as isSucc(
- 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
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
- Is there a perl-module that defines something similar to
- Does someone has an easier/faster/alternative implementation* of
* 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.