String Algorithms Flashcards
1
Q
What is the time complexity of checking if a string is a palindrome?
A
O(n)
2
Q
What is the KMP algorithm used for?
A
Pattern matching in O(n + m) time.
3
Q
What is the Rabin-Karp algorithm?
A
Uses hashing for fast pattern search.
4
Q
What is the Boyer-Moore algorithm used for?
A
Skips unnecessary comparisons in pattern matching.
5
Q
What is the longest palindromic substring problem, and how is it solved efficiently?
A
Solved with dynamic programming or Manacher’s algorithm.
6
Q
How can a Trie be used for efficient string matching?
A
Stores words for efficient prefix searches.
