The Swap-Insert Correction distance from a string S of length n to another
string L of length m \ge n on the alphabet [1..s ] 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 s
of the alphabet. We describe an algorithm computing this distance in time
within O (s^2 nm g^{s-1}), where for each a in [1..s] there are n*a occurrences
of a in S, m*a occurrences of a in L, and where g= max a in [1..s ] min{n a , m
a - n a } is a new parameter of the analysis, measuring one aspect of the
difficulty of the instance. The difficulty g is bounded by above by various
terms, such as the length n of the shortest string S, and by the maximum number
of occurrences of a single character in S (max a in [1..s ] n a ). This result
illustrates how, in many cases, the correction distance between two strings can
be easier to compute than in the worst case scenario.