A. String Matching

Rabin-Karp Algorithm

Given a string with $m$

  1. Use hash function to compute the pattern’s hash value

Knuth-Morris-Pratt (KMP) Algorithm

B. Is Subsequence problem

Very Basic

image.png

C. Longest Palindrom Prefix problem

反转，“#”拼接，再用KMP