Problems Notes on Codeforces String Problems

My goal is to solve all the problems related to strings/hashing/suffix structure starting from rating 2600 in Codeforces. I will keep summarizing problem ideas here.

If a problems falls into a specific large category, I will summarize it in those independent blogs:
Palindrome Tree
Suffix Automaton
Hashing

Shortest/Longest Path Cut Vertex Checking1214D650D, MCPC19B
Sometimes, if we want to check if a vertex is neccesary for a shortest path/longest path, one way to do is hashing as mentioned in the hashing blog. Another much easier way is to group the vertices by distance. The vertex is the cut vertex if and only if it is the only one in that “distance level”.

Non-Palindrome Cutting: Timus 2057
Consider that the only “impossible” cases are like $aaaaa$, $aaaabaaaa$, or $abababa$ (not really sure how to prove, though).
Otherwise the minimum answer is either $1$ or $2$. Check it brute-forcely.
For the maximum answer, we have $dp[i] = max\{dp[j] + 1\}$ for all $j$ s.t. $s[j + 1, i]$ is possible to split. Then we do the dp transition by excluding the three impossible cases.

Reference:
1. URAL Palindromic Contest (in Chinese)

Learning notes on Palindrome Tree

Basic things this structure can do
  1. the number of distinct palindrome substring in a string (which turns out to be the number of extra states, which is linear)
  2. the number of times each palindrome appears
  3. The number of palindromes (or sum of the corresponding properties) that ends in a certain location.
Properties
  1. The size of the tree is $O(n)$. This is a result of the fact that at most one new distinct palindrome can be added when we add a new character. (Otherwise, choose the longest of them, $s_{longest}$, and the shorter one will definitely appear if we flip it from the middle point of $s_{longest}$.)
  2. Each fail pointer is pointing to a smaller index. So when we want to do tree DP, we can just use the index as the topological order.
Other tricks:

Adding characters from both sides: HDU 5421
To do such thing, we can keep a extra pointer at the begining of the string. Both pointer will be the longest palindrome prefix/suffix. The operations will be symmetric, and, additionally, when the new distinct palindrome we get is the new whole string, we need to update both pointer to keep the property of the pointers.

Series Link

To be continued…

About Suffix Automaton

Some Properties
  • Each state in the SAM corresponds an equivalent class of substrings of $s$ which appear in the same set of positions.
  • For some state $v$, $len(v) – minlen(v) + 1$ is the number of distinct substring in the corresponding class.
About String Matching

To check if $t$ occurs in $s$, we can keep matching $t$ on the SAM of $s$, go to the next state if the current character is matched, or get through suffix link otherwise.

If we want to know how much a string $t$ can be matched for each state in the SAM of $s$, we can first keep matching it and record whenever the character is matched, and then we can propagate the value through the links.

About Paths in the DAG

Fact: Every distinct path from the root is a distinct substring.

Following from this fact, we can use DP to calculate lots of things, such as number of distinct substrings, sum of distinct integers.
Example: sum of dictinct integers, Morse Code

About Suffix-Link Tree

The suffix links forms a tree in which you can propagate information upwards, like the first/last ocurring positions, number of characters matched in a suffix, etc.
Example: propagation of available indices

Related Problems

Sliding Windows for String Matching: HDU 6583
Analysis in the blog for the original contest.