AlgoScope

String

An array of characters, so most string algorithms are array algorithms with characters in the cells.

Data structures, data structure, beginner
Naive matching of a 6 character pattern in a 9 character text.txtpatabcabcabdabcabd

String Matching: Naive, every shift

Start, step 1 of 6

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.