String overlaps

The total numbers of strings with length n and k colors that cannot overlap themselves are given by

a[0]=1; a[n_]:= k a[n-1]-If[EvenQ[n],a[n/2],0]

Up to reversal and interchange of A and B, the first few overlap-free strings with 2 colors are A, AB, AAB, AAAB, AABB.

The shortest pairs of strings of 2 elements with no self- or mutual overlaps are {"A","B"}, {"AABB","AABAB"}, {"AABB","ABABB"}; there are a total of 13 such pairs with strings up to length 5, and 85 with strings up to length 6.

The shortest non-overlapping triple of strings is {"AAABB","ABABB","ABAABB"} and its variants. There are a total of 36 such triples with no string having length more than 6.