Page 146 - Data Structures Handout_Neat
P. 146
11.3.2 Basic Operations
Basic string operations include searching for a substring within a larger string,
matching patterns, and comparing two strings lexicographically. These operations form the
foundation for more advanced algorithms. For example, searching for a keyword in a
document or matching a regular expression against user input relies on these fundamental
techniques.
11.3.3 Knuth-Morris-Pratt (KMP) Algorithm
The KMP algorithm improves substring searching by avoiding redundant comparisons.
It preprocesses the pattern to create a partial match table, which guides the search process.
This results in a time complexity of ( + ), where is the length of the text and is the
length of the pattern.
Example in C++:
146
