6 subtopics · 19 problems
String Algorithms
Hashing, KMP, Z-function, tries, suffix structures, and string matching.
01Polynomial Rolling Hash
Compare substrings in O(1) after O(n) preprocessing.
1 easy1 medium2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1851CTiles Comeback | easy | Solve |
| 271DGood Substrings | medium | Solve |
| 1850GThe Morning Star | hard | Solve |
| 1200ECompress Words | hard | Solve |
02KMP Algorithm
Linear-time pattern matching using the prefix function.
2 medium1 hard
| Problem | Difficulty | Link |
|---|---|---|
| 126BPassword | medium | Solve |
| 625BWar of the Roses | medium | Solve |
| 432DPrefixes and Suffixes | hard | Solve |
03Z-Function
Compute Z-array: length of longest substring starting at i that matches a prefix.
1 medium2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 126BPassword | medium | Solve |
| 432DPrefixes and Suffixes | hard | Solve |
| 535DTavas and Malekas | hard | Solve |
04Trie (Prefix Tree)
Store and search strings/prefixes efficiently.
3 medium1 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1829CMr. Perfectly Fine | medium | Solve |
| 1881DDivide and Equalize | medium | Solve |
| 271DGood Substrings | medium | Solve |
| 1837DBracket Coloring | hard | Solve |
05Suffix Array & LCP
Sort all suffixes and compute longest common prefix array.
3 hard
| Problem | Difficulty | Link |
|---|---|---|
| 432DPrefixes and Suffixes | hard | Solve |
| 1200ECompress Words | hard | Solve |
| 802IFake News (hard) | hard | Solve |
06Manacher's Algorithm
Find all palindromic substrings in linear time.
2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1326D2Prefix-Suffix Palindrome (Hard) | hard | Solve |
| 7DPalindrome Degree | hard | Solve |
Was this helpful?