Lukas' Notes

computation

Definition

String Matching Problem

Given a text string and a pattern string over an alphabet . The string matching problem asks for all indices such that occurs in starting at position , i.e. .

Input:

Examples

occurs at indices and .

occurs at indices , , and . Occurrences may overlap.

does not occur in . The set of occurrences is empty.
Output: all occurrences of in