Proof. For a partition π(t) = {t1, t2, ..., tk} satisfying t ∈ Tj and π(t) ∈ Π(t, j), from the definition of Π(t, j), |tk-1tk| ≥ j. Since t is a suffix of s[1, j] and |t| ≥ |tk-1tk| ≥ j, we have t = s[1, j] and 1 ≤ k ≤ 2. Consider the self alignment of π(t) such that the last j letters in t are mapped to spaces with score . Two cases arise. Case 1: k = 1 and t = t1 = s[1, j]. In this case, the middle alignment is empty. Thus, V(π(t), c, j) =  × (|t1| + j) = c·j. Case 2: k = 2 and t = t1t2 = s[1, j]. In this case, the middle alignment is the alignment between |t2| spaces and t2. By the assumption that  >μ(Δ, x), V(π(t), c, j) = |t2| × μ(Δ, x) +  × (|t1| + j) <c·j. □