What
An pattern searching algorithm in linear time that uses dynamic programming.
Idea
- Calculate the LSP - Longest Suffix which is also a prefix for
p(pattern) - Match each character of
t(target) - If there is a mismatch, use the LSP to know which next character to match.
Implementation
Trick: equivalent to calculating lsp(p + sep + t) where sep is a character not in t or p
Complexity
- Time:
- Space:
Properties
- Matches multiple (
k) pattern take time. - Finding multiple matches does not increase complexity.