Let s = a1a2...an be a string of length n. A partition π(s) = {s1, s2, ..., sk} of s is a set of substrings of s such that s = s1s2...sk (si's are also called repeats). When s is clear, we use π instead of π(s). Π(s) denotes the set of all partitions of s. Let si and si+1 be two strings. The similarity measure μ(si, si+1) between si and si+1 is the maximum alignment value for si and si+1. For any two letters (possibly spaces) x and y, μ(x, y) is the similarity score between the two letters. For example, one can use the following score scheme I: a match costs 1, a mismatch costs -1, and an insertion or deletion costs -1. Here we choose to use maximization version since for protein sequences, there are popular similarity matrices, e.g., PAM matrix.