A fixedparameter algorithm for string-to-string correction

In the String-to-String Correction problem we are given two strings x and y and a positive inte-ger k, and are asked whether it is possible to trans-form y into x with at most k single character dele-tions and adjacent character exchanges. We present a first simple fixed-parameter algorithm for String-to-String Correction that runs in O∗(2k). More-over, we present a search tree algorithm that ex-hibits a novel technique of bookkeeping called charg-ing, which leads to an improved algorithm whose run-ning time is in O∗(1.62k).