Palindromes, Lyndon and string DP

Questions 1 to 5 of 8

1. 1. Manacher's loop for an odd center i inside the window [l, r] starts the radius at min(d1[l + r - i], r - i + 1), not at d1[l + r - i] alone. Why is the cap r - i + 1 needed?

   The copied palindrome around the mirror may reach past r, where nothing is known yet, so the start radius must stop at the window edge.d1 values are always odd, so the cap keeps the radius odd.The mirror index l + r - i can be negative, so the cap stops the array from reading below index 0.Without the cap, d1 would count the characters of the whole string twice.
2. 2. An AI counts the palindromic substrings of aaaa as sum(d1) + sum(d2). Which number should it print?

   Type a number.

3. 3. For the string abba, the program prints d1 = [1, 1, 1, 1] and d2 = [0, 0, 2, 0]. Which statements about the even-center array are true?

   Pick every answer that is true.

   d2 is [0, 0, 2, 0].d2[2] = 2 describes the palindrome s[0..3], which is abba.The length of the even palindrome at d2[2] is 2 * 2 - 1 = 3.The even palindrome bb sits in the gap between positions 1 and 2.
4. 4. An AI wrote the factor step of Duval's factorisation as res.push_back(s.substr(i, j - i)); and says the result is correct. On the input abcdba it prints abcdba and then a. What is wrong?

   Nothing is wrong, because the factors of abcdba are the whole string and a.abcdba is not a Lyndon word, since its proper suffix a is smaller than it. The factor length must be j - k = 5, which gives abcdb.The factor must always be one character long, so the output should be a, b, c, d, b, a.The loop never ends on abcdba, because j reaches the end of the string.
5. 5. A checker for the smallest rotation of abab compares the returned index with 0 only. An AI returns index 2 and the checker marks it wrong. What is the right judgement?

   Index 2 is wrong, because the rotation starting at 2 is baba, not abab.Index 2 is wrong, because Duval's method only ever returns the first index of a tie.Index 2 is only correct when the string length is odd, so abab must be rejected.Index 2 is correct, because the rotation starting at 2 is abab, equal to the one at 0. The checker should compare the rotation strings, not one index.