String
An array of characters, so most string algorithms are array algorithms with characters in the cells.
String Matching: Naive, every shift
Search "abcabcabd" for "abcabd". Try every alignment of the pattern under the text, from shift 0 to shift 3, comparing character by character and stopping at the first mismatch.
Cost
- Access
- O(1)
- Search
- O(n)
- Concatenate
- O(n + m)
- Space
- O(n)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
String Matching covers these too, in the same run.