This unit covers basic string processing: Some ad-hoc information, the trie datastructure, and the following string matching algorithms
- Naive (quadratic)
- Rabin-Karp (worst case quadratic, average case linear or worst case linear, with some error possibility)
- Z-algorithm (linear)
- Knuth-Morris-Pratt (linear)
Some complementary (not for Z-algorithm or Rabin-Karp) notes can be found in section 6 of the book Competitive Programming 3. Additional techniques can be found there as well
- Unit 1: Complexity
- Unit 4: Tree data structures
- UVa 10115 - Automatic Editing
- UVa 10361 - Automatic Poetry
- UVa 10082 WERTYU
- UVa 1368 DNA Consensus String
- UVa 902 - Password Search
- UVa 755 - 487--3279
- Codechef - Remember the recipe
- UVa 363 - Approximate matches
- UVa 455 - Periodic strings
- UVa 1223 - Editor
- Codeforces 126 - problem B
- UVa 11151 - Longest Palindrome
- UVa 11475 - Extend to Palindrome