Content deleted Content added
Move up notice, other rewording |
|||
Line 5:
== Shifting substrings search and competing algorithms ==
The basic problem the algorithm addresses is finding a fixed substring of length ''m'' within a text of length ''n''; for example, finding the string "sun" in the sentence "Hello sunshine in this vale of tears." The simplest conceivable algorithm for this task just looks for the substring at all possible positions:
{{wikicode}}
'''1''' '''function''' NaiveSearch(''string'' s[1..n], ''string'' sub[1..m])
Line 13 ⟶ 14:
'''6''' '''return''' i
'''7''' '''return''' not found
This algorithm works well in many practical cases, but fails spectacularly on certain examples, such as searching for a string of 10,000 "a"s in a string of 10 million "a"s, in which case it exhibits its worst-case [[Big-O notation|Ω]](''mn'') time.
| |||