The Swap-Insert Correction distance from a string S of length n to another
string L of length m >= n on the alphabet [1..d] is the minimum number of
insertions, and swaps of pairs of adjacent symbols, converting S into L.
Contrarily to other correction distances, computing it is NP-Hard in the size d
of the alphabet. We describe an algorithm computing this distance in time
within O(d2nmgd-1), where there are na occurrences of a in S, ma occurrences of
a in L, and where g=max_{a in [1..d]} min{na,ma-na} measures the difficulty of
the instance. The difficulty g is bounded by above by various terms, such as
the length of the shortest string S, and by the maximum number of occurrences
of a single character in S. Those results illustrate how, in many cases, the
correction distance between two strings can be easier to compute than in the
worst case scenario.