How to "align" 2 strings?

Question

First let me explain what I mean by "alignment".

Let's say we have to strings : e.g. AGBCDEF ABCDIEFK

Their "alignment" would be :

A - G - B - C - D -   - E - F -
A -   - B - C - D - I - E - F - K
-----------------------------------

A - ? - B - C - D - ? - E - F - ?

Another (quite simplified) example (since I believe my question has probably something to do with NLP) :

I give Mary a kiss
I give Ann a book
----------------------
I give X a Y

How would you go about that? Any ideas (or even reference) regarding the algorithm?

I'm probably going to write this in Objective-C (or PHP), but any code would be welcome.

Answer 1

I think what you're looking for is something like minimum edit distance from natural language processing. Look at a demo of the Levenshtein distance algorithm here

Answer 2

I think what you are looking for is longest common subsequence.