BINPALIN - Editorial


Author: Sidhant Bansal
Tester: tncks0121


Strings, Hashing.


Consider an initially empty binary string. There are n queries. In each query, you are asked to either add a character 0/1 or remove the last character. After each query, find the largest palindromic substring of the string.


Consider a base B and a prime mod. Precompute all powers upto n of B modulo mod. Also compute the powers of inverse of B upto n.

Let the current string be s_{0}s_{1} \ldots s_{L-1}. Let p_i be the largest palindromic substring of the prefix of length i. Maintain prefix hash of the string, H_i = \displaystyle \sum_{j=0}^{i} (s_j + 1) B^{i - j} .

Also maintain another set of prefix hashes found using modular inverse of B as the base. That is, also maintain G_i = \displaystyle \sum_{j=0}^{i} (s_j + 1) B^{j - i} .

Now, the hash of a substring s_l...s_ r is H_r - H_{l-1} B^{r - l + 1}, and the hash of the reverse of this substring, s_r \ldots s_{l} is \displaystyle B^{r - l} (G_r - G_{l-1} B^{l - r - 1}).

Using precomputed powers, both the hashes and reverse hashes can be found in O(1). Also, the arrays H and G can be maintained in O(1) per query, using H_i = H_{i - 1} B + s_i + 1 and G_i = G_{i-1} B^{-1} + s_i + 1.

Now, say the current largest palindromic substring is t. On appending a new character, the new longest palindromic substring has to have length \leq t + 2, as otherwise removing the first and last characters from this substring would give a palindromic substring of length > t in the original string, which is a contradiction.

So, on every append query, we only have to test whether the suffixes of length t + 1 and t + 2 are palindromes, which can be done in O(1). So, overall we can update p, H, G in O(1).

On each delete query, we just have to remove the last element from each of the arrays p, H, G.

The overall complexity would be O(n).


Author’s solution can be found here
Tester’s solution can be found here