UPD:Thanks to comment from arvindf232 and pajenegod, the blog has been developed with the help of Chatgpt. Hope that such a development will make this blog more readable.
Written before
In this blog, I want to share Border Theory, a useful and elegant insight about string borders that often appears in competitive programming. Although this idea deserves to be as well-known as the KMP algorithm, many people today aren’t aware of it or how to use it to speed up their solutions.
Main Theoretical Result of Border Theory
Conclution
For a string $$$S$$$, a border is a substring that is both a prefix of $$$S$$$ and a suffix of $$$S$$$.
For a string $$$S$$$, we define that:
is the sequence of all lengths of the border of $$$S$$$, sorted in increasing order.
According to the theory,it's garenteed that for all possible $$$S$$$, $$${B_i}_{i = 1}^n$$$ can be partitioned into $$$\operatorname{O}(\log |S|)$$$ continuous subsequences where each subsequence forms an arthmetic progressions.
Proof
First of all,if there's a border $$$T$$$ of $$$S$$$ that $$$2|T| \ge |S|$$$, Then all the positions where $$$T$$$ occur in $$$S$$$ follow an arthmetic pattern.
Second, All border lengths satisfying that inequality also appear in an arithmetic sequence:
Using the two lemma we can proof that for every two border length $$$x,y(x \lt y)$$$ not in the same subsequence, $$$2x \lt y$$$ is garenteed, making the theory right.
Practicle way to use border theory:Shlink pointer
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]];
When we tries to analyze on borders,we found that:
In an arthmetic progression of the border of a prefix of length $$$i$$$ in $$$S$$$,the differance between to arthmetic progression and a similar one at $$$i - diff$$$ are a new border of length $$$i - diff_i$$$ and a new position that a border occurs as suffix $$$i - len_{shlink_i} - diff_i$$$. Which is really convenient to make use of Border Theory.
One example
Given up to $$$5$$$ test cases,each with 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 construct a new string $$$Y$$$ in the two ways: - Append the full string $$$T$$$ and $$$S$$$ and form a string with length $$$|T| + |S|$$$; - If a suffix $$$A$$$ in $$$T$$$ is also a prefix of $$$S$$$, you can overlap them and construct a string of length $$$|T| - |A| + |S|$$$.
Find the number of distinct length of strings in the range $$$[1,w]$$$ that can result from the process.
Extention to palindromic suffixes
As we found that The borders of palindormes are also the palindromic suffixes of a palindrome, then we can say that for a string $$$S$$$, the sequence of the lengths of all palindromic suffixes in increasing order can be partitioned into $$$\operatorname{O}(\log |S|)$$$ continuous arthmetic progressions. We can also say that the sequence of the lengths of all even-length palindromic suffixes in increasing order can be partitioned into $$$\operatorname{O}(\log |S|)$$$ continuous arthmetic progressions.
Tasks
In 932G - Palindrome Partition 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 when the string is the prefix of length $$$i$$$ in the string $$$T$$$, then we use shlink pointers to speed it up.
Such solution is similar to 906E - Reverses,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
Though bruteforce on borders is slow, we can approach using border theory,that shows that border lengths cluster into structured arithmetic sequences bounded in number by $$$\operatorname{O}(\log |S|)$$$ to make it much faster.
