I am trying to compute the shortest binary string that contains all binary palindrome of length n as substring. For example, for n=3, 00010111 is such a shortest string. However, brutal force performs really bad even for n=6, n=7 etc. Is there any optimization like branch and bound I can do here. My current optimization is following:
Use common super sequence algorithm to get an upper bound of the target string
palindrome of all 0 and all 1 is contained there hence we can place the first n position as 0 and last n position as 1
a continuous block of more than n-2 "1"s or "0"s is clearly not in shortest target string, hence this kind of situation should be avoided.
However, the above optimization is not enough, the program cannot even terminate in reasonable time for n=7.
Hence I am asking if anyone can get some further optimization