Editorial for COCI '21 Contest 6 #4 Palindromi
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, we can iterate over all substrings of the new string after each concatenation and check (e.g. using hashing) how many different palindromes there are. In this way, for a word of length , we can find the number of subpalindromes in so the total time complexity is . We can notice that when connecting two strings, it is enough to iterate over only the substrings which begin in the first word and end in the second one. In this way, connecting two words of length and is done in , which turns out to be in total, solving the second subtask.
The following fact is useful for the remaining subtasks: if we append a character to any string to the left or to the right, the number of different palindromes of will increase by at most . Consequently, the total number of distinct palindromes in a string of length can be at most . Furthermore, there exists a data structure which maintains all the different subpalindromes of a string and the relations they have to each other. This data structure is called a palindromic tree or eertree. As mentioned, there are subpalindromes and it's possible to maintain this data structure using space and amortized time.
In short, each subpalindrome of is represented by a node. If is a subpalindrome of and is a character such that is also a subpalindrome of , then there is an edge between and labeled with . Additionally, for each subpalindrome , we'll have a suffix link towards the longest proper suffix of which is also a palindrome. The eertree supports the operation which appends the character to the end of the current string . This function can be implemented in amortized in the following way: at all times, we maintain the longest suffix of the current string which is also a palindrome. When adding the character , if there is another character in front of , we simply extend to . Otherwise, we iterate through the suffix link chain until we find the first palindrome in front of which is . Implementing this idea (according to the link provided above) was sufficient for the third subtask.
For the final subtask, we need to make a couple of modifications:
- Instead of the time complexity of being amortized , we can make it so that it is (non-amortized) , where is the alphabet size. In our case, the alphabet consists only of the characters
0
and1
, so we consider the time complexity to be . Along with , it is enough to keep track of two additional values: and , which represent the longest proper suffix in front of which is the character0
or1
respectively. All the mentioned values can be computed in when adding a new node. - Instead of having a function which adds the character to the right, we'll support adding character both to the left and to the right. To do this, we maintain both the longest prefix and the longest suffix palindrome of the current string. When adding a character to the right, this affects only the longest suffix palindrome, and when adding it to the left it affects only the longest prefix palindrome. The only exception is when the entire string becomes a palindrome, in which case the longest prefix and suffix palindromes are equal and are equal to the entire string. Since the time complexity is no longer amortized, appending to both sides is done in .
- We'll append the smaller string to the larger string. If the right string is smaller than the left string, we successively add characters from the right string to the right end of the left string. If the left string is smaller, we successively add characters from the left string to the left end of the right string. It can be shown that the number of times a character gets added to a string is , and since we have a data structure which supports these additions in , the total time complexity is also .
Comments