~~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 Checking**: 1214D, 650D, 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)