0
$\begingroup$

Let an integer n be given. Write the integers from 1 to n in binary notation successively from left to right. In the resulting string consisting of zeros and ones, choose a palindrome substring of maximal length. It is required to find the length of this substring. For example, if n=5, we can get a string which is 1 10 11 100 101. And we can get the longest substring that is palindromic: 11011 or 01110. So the answer to the question is 5. The n can be very big. Are there any good algorithm to solve this problem? Thanks in advance!

$\endgroup$
  • $\begingroup$ Unless your integer fits into a word this should be equivalent to the general longest palindromic substring problem $\endgroup$ – Niklas B. Mar 9 '14 at 5:31
2
$\begingroup$

You could use a regular palindrome substring search algorithm, such as as Manache's Algorithm. It would still be optimal, i guess, even considering that your string is binary. Take a look at that algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.