Strings & Automata

These are the classic algorithms for matching and comparing text faster than checking every position. KMP and the Z-algorithm find patterns in linear time, Manacher finds palindromes, and hashing lets you compare substrings in constant time.

It is the smallest plan, 31 problems over nine chapters: KMP, Z-algorithm, Manacher, string hashing, minimum rotation, Aho-Corasick, suffix arrays and automata, subsequence automata, and advanced techniques. It suits anyone who has met these names in editorials and wants to practice them on real problems.

31 problemsRating 1167–26059 Chapters

Open the study room

Want company while you work through this list? Sign in, open the study room, and your heroine will bring you the problems one at a time.

I. KMP Algorithm

§1.1 Fundamentals

Problem	Rating
28. Find the Index of the First Occurrence in a String	Unrated
796. Rotate String	1167
1392. Longest Happy Prefix	1876
1764. Form Array by Concatenating Subarrays of Another Array	1588
1668. Maximum Repeating Substring	1396
459. Repeated Substring Pattern	Unrated
2800. Shortest String That Contains Three Strings	1856
214. Shortest Palindrome	Unrated
3529. Count Cells in Overlapping Horizontal AND Vertical Substrings	2105
686. Repeated String Match	Unrated
3455. Shortest Matching Substring	2303

II. Z-Algorithm

§2.1 Fundamentals

Problem	Rating
2223. Sum of Scores of Built Strings	2220
3474. Lexicographically Smallest Generated String	2605

§2.2 LCP Array

Problem	Rating
2430. Maximum Deletions on a String	2102

III. Manacher's Algorithm

§3.1 Fundamentals

Problem	Rating
5. Longest Palindromic Substring	Unrated
647. Palindromic Substrings	Unrated
214. Shortest Palindrome	Unrated
1745. Palindrome Partitioning IV	1925

§3.2 Center Expansion Method

Problem	Rating
5. Longest Palindromic Substring	Unrated
2472. Maximum Number of Non Overlapping Palindrome Substrings	2013

IV. String Hashing

§4.1 Fundamentals

Problem	Rating
28. Find the Index of the First Occurrence in a String	Unrated
187. Repeated Dna Sequences	Unrated
1316. Distinct Echo Substrings	1837
2261. K Divisible Elements Subarrays	1724
1044. Longest Duplicate Substring	2429
718. Maximum Length of Repeated Subarray	Unrated

V. Minimum String Rotation

§5.1 Fundamentals

Problem	Rating
899. Orderly Queue	2097
1625. Lexicographically Smallest String After Applying Operations	1992

VI. Aho-Corasick Automaton

§7.1 Fundamentals

Problem	Rating
1032. Stream of Characters	1970
1408. String Matching in an Array	1223

VII. Suffix Array & Automaton

§8.1 Fundamentals

Problem	Rating
1163. Last Substring in Lexicographical Order	1864
1754. Largest Merge of Two Strings	1829
1044. Longest Duplicate Substring	2429
718. Maximum Length of Repeated Subarray	Unrated
1408. String Matching in an Array	1223
1316. Distinct Echo Substrings	1837

VIII. Subsequence Automaton

§9.1 Fundamentals

Problem	Rating
792. Number of Matching Subsequences	1695

IX. Advanced String Techniques

§10.1 Advanced

Problem	Rating
466. Count the Repetitions	Unrated

This is the last plan on Track 1; once its core sections are done, the route moves on to Track 2 and recursion.

Ratings come from zerotrac's LeetCode contest ratings. Some problems have no zerotrac rating and are marked Unrated.

Open the study room