I need to implement the Ratcliff-Obershelp (aka Gestalt Pattern Matching) algorithm and I'm stuck at building the recursive part.
I have built the lcs (longest common substring) intermediate function (using dynamic programming), now i need to apply it to the 2 compared strings.
Example:
lcs("WIKIMEDIA", "REMEDY") = "MED"
Taking both sides (left-right) of each string, the new string chunks to compare:
("WIKI", "RE") and ("IA", "Y");
both return lcs = 0, but i need to implement this in an recursive way, as the 2 initial strings may result in 4 chunks to "lcs"-compare, and then 8, etc.
The exit condition would be either "lcs = 0" or "one of the strings is empty" (preferred over the former condition) Any pseudo code would help. Thanks!