Boyer-Moore string search: Difference between revisions
Add description of this algorithm.
m (→{{header|Python}}: fix docs from original) |
(Add description of this algorithm.) |
||
Line 1:
{{draft task}}
;Task:
[https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm < About this algorithm >]▼
<br>
This algorithm is designed for pattern searching on certain types of devices which are backtracking-unfriendly such as [https://en.wikipedia.org/wiki/Tape_drive Tape drives] and [https://en.wikipedia.org/wiki/Hard_disk_drive Hard disk].
Its works by first caching a segment of data from storage and match it against the pattern from the highest position backward to the lowest, if the matching fails, cache next segment of data, and move the start point forward to skip the portion of data which will definitely fail to match, until we successfully match the pattern or the pointer exceeds the data length.
▲[https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm
To properly test this algorithm, it would be good to search for a string which contains repeated subsequences, such as <code>alfalfa</code> and the text being searched should not only include a match but that match should be preceded by words which partially match, such as <code>behalf</code>.
| |||