Palindrome counts and cuts

Questions 1 to 5 of 8

1. 1. What does this program print? ``python def count_by_expanding(s): n = len(s) count = 0 for i in range(2 * n - 1): left = i // 2 right = left + (i % 2) while left >= 0 and right < n: if s[left] != s[right]: break count += 1 left -= 1 right += 1 return count print(count_by_expanding('abcbab')) ``

   6798
2. 2. What does this program print? ``python def build_palindrome_table(s): n = len(s) is_pal = [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]): is_pal[i][j] = True return is_pal def pieces(s): n = len(s) if n == 0: return [] is_pal = build_palindrome_table(s) cut = [0] * n start = [0] * n for i in range(n): if is_pal[0][i]: cut[i] = 0 start[i] = 0 continue best = float('inf') best_start = -1 for j in range(1, i + 1): if is_pal[j][i] and cut[j - 1] + 1 < best: best = cut[j - 1] + 1 best_start = j cut[i] = best start[i] = best_start result = [] end = n - 1 while end >= 0: begin = start[end] result.append(s[begin:end + 1]) end = begin - 1 result.reverse() return result print(pieces('abcca')) ``

   ['abcca']['a', 'bcca']['abc', 'c', 'a']['a', 'b', 'cc', 'a']
3. 3. How many centres does racecar have? It has 7 letters.

   Type a number.

4. 4. Which statements about the two palindrome methods are true? Select all that apply.

   Pick every answer that is true.

   On a string of one repeated letter, both methods do about n squared workThe table method needs about n squared cells of memory, while expanding around centres needs no tableExpanding around centres needs an n by n boolean table to remember each palindromeA string of n letters has 2n minus 1 centres, so the expansion loop runs 2n minus 1 times
5. 5. Why does the loop use left = i // 2 and right = left + (i % 2)?

   It runs one loop over both letter centres (odd length) and gap centres (even length)It skips every second centre to save timeIt converts i into a letter index for indexing the stringIt keeps left from going below 0