Partial string matching algorithms

Question

Good morning,

Does anyone know about efficient algorithms for partial string matching? For example, given the two strings "woods" and "woodes", the algorithm could/should possibly return "wood+s", or " | e".

Thank you very much.

Answer 1

that's a quite complex problem and named "sequence alignment problem". do you want to implement it by yourself? for a first look wikipedia provides a nice article: http://en.wikipedia.org/wiki/Sequence_alignment

Answer 2

Search for "Levenshtein algorithm" and/or "diff algorithm" on stackoverflow.