What is an overlap pattern?

An overlap pattern is a binary string that describes how a given character string overlaps shifted copies of itself.  For example, consider the string "abc".

Its overlap pattern is "100".  For short, op("abc") = "100".  Here's another couple of examples:

As we see, op("aba") = 101. 

And op("aabaa") = "10011".   

 

For a string s of length n, with characters indexed from 0 to n-1, the kth digit of op(s) = 1 if and only if the first n-k characters of s match its last n-k characters (in order.)  Notice that since every string matches itself, every overlap pattern starts with "1".

What is an overlap pattern table?

There is an OP table for every positive integer.  (We can debate whether or how to define one for n = 0.)  It consists of every possible overlap pattern of length n, arranged in increasing numeric order.  For n = 1, every string s of length 1 has op(s) = "1", so OP table n = 1 consists of "1" by itself.

For strings of length 2, there are two possible overlap patterns, and OP table n = 2 is ("10", "11").  (Examples: op("aa") = "11", and op("ab") = "10".)

OP table n = 3:

100

101

111

n = 4:

1000

1001

1010

1111

n = 5:

10000

10001

10010

10011

10101

11111

By representing 1's with black squares, we can visualize these tables more graphically.

n = 6:

I have found that reflecting these images around the center line of the last column seems to bring out the patterns:

This is a brief introduction; any questions are welcome.