CS136 Study Guide - Linear Motor, Nipple
Document Summary
Pattern matching/string search: find the location(s) of a short string (the pattern) in a longer string (the text). Example: find the pattern p = needle in the text t = haystackneedlehaystack. Brute force: check every possible location in t to see if p is there. Example: search for p = abc in t = abdacabcd. Try each possible location 0, 1, . in p , and see if abc starts there. Once a mismatch occurs, move on to the next location. a b d a c a b c d (cid:88) (cid:88) b a c a . 5 (cid:88) (cid:88) a b a (cid:88) a (cid:88) b (cid:88) c. Loop over two indices: position" or t -index and mismatch" or p -index. Analysis: say |t| = n and |p| = m. There are n m + 1 positions to check, and each position can have up to m character comparisons.
