String-Searching/Matching Algorithms
- are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text
Algorithm - Types
Single-Pattern Algorithms
- 𝑚 is the length of the pattern
- 𝑛 the length of the searchable text
- 𝑘 = |𝛴| is the size of the alphabet
|
Algorithm |
Preprocessing Time |
Matching Time |
Space |
|---|---|---|---|
|
Naïve algorithm |
none |
𝛩(𝑚𝑛) |
none |
|
𝛩(𝑚) |
Θ(𝑛) in average, |
𝛰(1) | |
|
𝛩(𝑚) |
𝛩(𝑛) |
𝛩(𝑚) | |
|
𝛩(𝑚 + 𝑘) |
𝛺(𝑛/𝑚) at best, |
𝛩(𝑘) | |
|
𝛩(𝑚) |
𝛰(𝑛) |
𝛰(1) | |
|
Backward Non-Deterministic DAWG Matching (BNDM) |
𝛰(𝑚) |
𝛺(𝑛/𝑚) at best, | |
|
Backward Oracle Matching (BOM) |
𝛰(𝑚) |
𝛰(𝑚𝑛) |