Revision as of 23:26, 16 March 2023 edit LachlanA (talk \| contribs) Extended confirmed users 1,854 edits →Single-pattern algorithms: two-way has space complexity log(m). Saying "O(1) because string lengths are bounded in practice" makes O(.) notation useless. ← Previous edit		Revision as of 21:41, 8 April 2023 edit undo Skyerise (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 149,364 edits →Naive string search: 's -> is Next edit →
Line 42: == Examples of search algorithms == === Naive string search === A simple and inefficient way to see where one string occurs inside another is to check at each index, one by one. First, we see if there's is a copy of the needle starting at the first character of the haystack; if not, we look to see if there's a copy of the needle starting at the second character of the haystack, and so forth. In the normal case, we only have to look at one or two characters for each wrong position to see that it is a wrong position, so in the average case, this takes [[Big O notation\|O]](''n'' + ''m'') steps, where ''n'' is the length of the haystack and ''m'' is the length of the needle; but in the worst case, searching for a string like "aaaab" in a string like "aaaaaaaaab", it takes [[Big O notation\|O]](''nm'') === Finite-state-automaton-based search ===

String-searching algorithm: Difference between revisions