26-string-processing

Unit 26: String processing

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

Prerequisites

• Unit 1: Complexity
• Unit 4: Tree data structures

Practice problems

Ad hoc

• UVa 10115 - Automatic Editing
• UVa 10361 - Automatic Poetry
• UVa 10082 WERTYU
• UVa 1368 DNA Consensus String

Tries

• UVa 902 - Password Search
• UVa 755 - 487--3279
• Codechef - Remember the recipe

String matching

• UVa 363 - Approximate matches
• UVa 455 - Periodic strings
• UVa 1223 - Editor
• Codeforces 126 - problem B
• UVa 11151 - Longest Palindrome
• UVa 11475 - Extend to Palindrome