GryllsP's blog

Strings
By GryllsP, history, 7 weeks ago, In English

What are some good string algorithms that everyone should know in competitive programming?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

KMP and Trie

good luck!

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. String Matching
  2. String Sorting
  3. Regular Expressions
  4. Kunath-Morris-Pratt(KMP) algorithm
  5. Boyer-Morre Algorithm
  6. Robin-Karp Algorithm
  7. Z-Algorithm
→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Although you have to take some precaution against getting hacked on codeforces, I don't think there's a more versatile string algorithm than the polynomial rolling hash. It's a relatively simple algorithm that allows you to carry over your knowledge of prefix sums (which everyone should already have quite a lot of experience with) and apply them to string problems.

→ Reply