I am exploring the following combinatorial question about binary strings and would like insights, ideas, or references from the community.
For a binary string S of length N, define its border sequence as the strictly increasing sequence of integers x (1 ≤ x ≤ N) such that the prefix of S of length x equals the suffix of S of length x.
Formally: x is in the sequence if S[1..x] = S[N−x+1..N]
Note that x = N is always included.
Example: S = "01010" (N = 5) Border sequence = (1, 3, 5)
Now define f(N) as the number of distinct border sequences that occur among all binary strings of length N. We count only unique sequences, not strings.
Is there an optimal way to find this for given N rather than brute enumeration?
