Chapter 3.10: String Algorithms

English translation of this chapter is coming soon. Please refer to the Chinese version for now.

Content Outline

3.10.1 Why Do We Need Dedicated String Algorithms?

• Problem Introduction
• Issues with the Naive Algorithm
• KMP's Core Insight

3.10.2 Prefix Function (pi Array)

• Definition
• Intuitive Understanding
• Uses of pi Values

3.10.3 Efficient Construction of the Prefix Function

• Naive Method: O(N^2) or O(N^3)
• KMP's Key Observations
• Mismatch Jump Visualization
• Final Algorithm Implementation

3.10.4 KMP String Matching

• Core Technique: Concatenated String
• Complete Implementation
• Detailed Trace Example

3.10.5 Advanced KMP Applications

• Finding the Shortest Period of a String
• Counting Occurrences of Each Prefix
• Algorithm Comparison Table

3.10.6 Trie Tree (Prefix Tree)

• What is a Trie?
• Visualization
• Array Implementation of Trie
• Detailed Trace: Inserting "app" and "apple"

3.10.7 Classic Trie Applications

• Word Frequency Counting (Trie with Counting)
• 01-Trie for Maximum XOR Value

Common Mistakes

Exercises

1. Implement strStr (KMP)
2. Word Lookup (Trie)
3. Longest Common Prefix
4. Minimum Period of a String
5. Maximum XOR of Any Two Numbers in an Array
6. Phone Number Lookup (Prefix Conflict Detection)
7. Count Substrings Appearing at Least Twice
8. Maximum XOR Path on a Tree (Tree Path + 01-Trie)