UPD:Thanks to comment from arvindf232 and pajenegod,I rewrote parts of this post to improve clarity with the help of Chatgpt. I hope it reads more smoothly now.
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
Main Result
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 a string $$$T$$$ is a border of $$$S$$$ and $$$2|T| \ge |S|$$$, Then all positions where $$$T$$$ occurs in $$$S$$$ form an arthmetic progression.
Second, All border lengths satisfying $$$2 \cdot length \ge |S|$$$ also appear in an arithmetic sequence:
Using the two observations, we can show that for every two border length $$$x,y(x \lt y)$$$ do not lie in the same arithmetic subsequence, then $$$2x \lt y$$$, making the theory right.
Practical Use: The Series-Link (shlink) Trick
A practical formulation of this theory is the series link (often written shlink), which groups borders into arithmetic sequences so they can be processed efficiently.
We compute shlink[i] as the start of the next arithmetic progression. (Here link[i] is the usual border/failure link in KMP-style structures, len[i] is the length of the represented substring, and diff[i] is the differance of length between i and link[i].) Now $$$shlink_i$$$ 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 the arthmetic progression and a similar one at $$$i - diff$$$ are a new border of length $$$i - diff_i$$$ and a new start position $$$i - len_{shlink_i} - diff_i$$$. This allows us to jump across long chains of borders in limited steps.
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.
