Блог пользователя GryllsP

Strings
Автор GryllsP, история, 2 недели назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
2 недели назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

KMP and Trie

good luck!

→ Ответить
»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  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
→ Ответить
»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить