I am wondering if a constrained insert-only form of Levenshtein distance has been implemented before by someone? In my particular use case, all other operations should not count as they are not possible. Only parts of the strings can be stripped off. As an example, if our library has "Hello" and "complex".

These strings can be stripped and we might only see "Hel" or "llo" or "com" etc. I want to explore, if what we see is part of a sequence in our library.

Thanks for any suggestions.

  • 3
    $\begingroup$ I don't understand your example. What is the input, and what is the output? Give examples. Edit your question rather than answer it in the comments. $\endgroup$ – Yuval Filmus Dec 21 '16 at 14:31
  • 1
    $\begingroup$ Are you maybe looking for the Longest Common Subsequence? $\endgroup$ – adrianN Dec 21 '16 at 15:17

Your problem appears to be:

  • Given strings $S,T$, determines whether $S$ appears as a subsequence of $T$.

There are several ways you could approach this.

One way is to use dynamic programming and apply a straightforward modification to computing the Levenshtein edit distance, where you set the cost of an insertion to be 1 and the cost of a deletion or replacement to be $\infty$.

Another solution to use a string-matching algorithm. Build the regexp $.\star S_1 .\star S_2 . \star \cdots . \star S_n . \star$ and check whether $T$ matches this regexp, using any standard method (e.g., convert the regexp to a NFA or DFA). For instance, if $S$ is the string HOT and $T$ is the string HELLO THERE, then you will check whether HELLO THERE matches the regexp .*H.*O.*T.*. I suspect this might be faster, but the best way to find out is to try it and see.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.