申論題

1. A string matching algorithm aims to find the occurrence of a string P within another string (5%)

(5%) (b) The Knuch-Morris-Pratt (KMP) algorithm is a string matching algorithm designed to reduce redundant symbol comparisons in string matching. What is the big-O time complexity, in terms of N_P and N_s, of the KMP algorithm?