Written before
Border Theory,which was not well-known enough,should have been publicized together with KMP or similar algorithms.But nowadays lots of people don't know such a theory exist,making them unable to solve several tasks easily or even can't get a fast solution.So it's time to complete the blog as what I will do on this.
Formal Border Theory
Conclution
For a string $$$S$$$, There are a squence of strings:
it's garenteed that there exist a way to divide the sequence into $$$\operatorname{O}(\log |S|)$$$ continuous arthmetic progressions.
Proof
First of all,we found that if there's a string $$$T$$$ as a border of $$$S$$$ and $$$2|T| \ge |S|$$$, Then the occurrence of $$$T$$$ in $$$S$$$ forms an arthmetic progression.
Second,We found that all lengths of border $$$T$$$ that $$$2|T| \ge |S|$$$ will form an arthmetic progression:
So there's a way that if $$$p \lt q,p,q \text{ are the length of borders}$$$ not in the same continuous arthmetic progression, $$$2p \lt q$$$ exist,So the conclution is right.
Task
Given at most $$$5$$$ cases in a test case,each cases gives a string $$$S(1 \le |S| \le 5 \times 10 ^ 5)$$$ and an integer $$$w(1 \le w \le 10 ^ {18})$$$, when we have a string $$$T$$$ we can make the new string by $$$|T| + |S|$$$ or if a suffix $$$A$$$ in $$$T$$$ is also the prefix of $$$S$$$, replacement from $$$A$$$ to $$$S$$$ can be done as there's a string of length $$$|T| - |A| + |S|$$$.Find the number of distinct length of strings in $$$[1,w]$$$ can be formed.
Extention to palindromic suffixes
As we'll found that The borders of palindormes are also the palindromic suffixes of a palindrome, then we can say that for a string $$$S$$$, the lengths of palindromic suffixes form $$$\operatorname{O}(\log |S|)$$$ continuous arthmetic progressions. We can also say that the lengths of even-length palindromic suffixes form $$$\operatorname{O}(\log |S|)$$$ continuous arthmetic progressions.
Shlink pointer
introduction
As $$$shlink_i$$$ means to a node $$$i$$$,which node is the start of the next arthmetic sequence,can be calculated like this:
//define shlink[i]
//define link[i] as the maxinum border of i like fail pointers in KMP or PAM
//define len[i] as the length
//define diff[i] as the differance of length between i and link[i]
shlink[i] = link[i];
diff[i] = len[i] - len[link[i]];
if(diff[i] == diff[link[i]])
shlink[i] = shlink[link[i]];
Then we'll find:
Which is a good way to make use of Border Theory.
Tasks
In 932G - Палиндромное разбиение we can make a string $$$T$$$ by:
- $$$t_{2k - 1} = s_{k}$$$
- $$$t_{2k} = s_{n - k + 1}$$$
Then we found that The task turns to the number of ways to divide $$$T$$$ into several even-length palindromes, we tries to solve it using dynamic planning as $$$dp_i$$$ is the answer of the prefix of length $$$i$$$, then we use shlink pointers to make it $$$\operatorname{O}(|S| \log |S|)$$$.
Such solution is similar to 906E - Перевороты,which turns:
- $$$t_{2k - 1} = x_k$$$
- $$$t_{2k} = y_k$$$
And use dynamic planning to get the divition to even-length palindromes with least palindromes not with the length of $$$2$$$.
Summary
Sometimes we found that our solution is slow because we may have to bruteforce on borders. But when using the theory,we may found that the solution solvable and easy instead of other solutions that might be complex.
