On Binary Island, the locals have only two letters in their alphabet: A and B. Sequences of these letters are called strings. The number of letters in a string is called its length. If a string has length n, then we call it an n-string. For example, ABAABABAABAA is a 12-string. A block of consecutive letters in a string is called a substring. A substring may appear more than once. For example, ABAABABAABAA contains the substring AA three times, the substrings AB and BA four times each, but does not contain the substring BB. A string that reads the same forwards and backwards is called palindromic. Every 3-string starting with A has exactly three different palindromic substrings, as shown in this table. as shown in this image(please open)
a) Explain why it follows from the table above that every 3-string starting with B has exactly 3 palindromic substrings.
b) Show that every 4-string starting with A has exactly 4 palindromic substrings.
c) Show that every 5-string has exactly 5 palindromic substrings.
It is also true that every 6-string has exactly 6 palindromic substrings, and every 7-string has exactly 7 palindromic substrings. However, this pattern does not continue. d Find an 8-string that starts with AABBA and has only 7 palindromic substrings.
d) Find an 8-string that starts with AABBA and has only 7 palindromic substrings.
a) Flip all the letters in the table (change A to B and change B to A). Then you will get a list of 3-strings starting with B, and their palindromic substrings.
b) and c) can be done by inspection
d) AABBA already has A, B, AA, BB, ABBA. Extending to AABBABA adds ABA and BAB. Finally extending to AABBABAA adds no more palindromic substrings.