Content deleted Content added
→Use of hashing for shifting substring search: reverting the RK pseudocode on obtaining an initial hash value |
-wikicode |
||
Line 6:
The basic problem the algorithm addresses is finding a fixed substring of length ''m'', called the ''pattern'', within a text of length ''n''; for example, finding the string "sun" in the sentence "Hello sunshine in this vale of tears." One very simple algorithm for this task just looks for the substring at all possible positions:
'''1''' '''function''' NaiveSearch(''string'' s[1..n], ''string'' sub[1..m])
'''2''' '''for''' i '''from''' 1 '''to''' n
| |||