Content deleted Content added
Enervation (talk | contribs) |
Enervation (talk | contribs) →Applications: Fix out of bounds error, probably |
||
Line 183:
The suffix array of a string can be used as an [[Index (search engine)|index]] to quickly locate every occurrence of a substring pattern <math>P</math> within the string <math>S</math>. Finding every occurrence of the pattern is equivalent to finding every suffix that begins with the substring. Thanks to the lexicographical ordering, these suffixes will be grouped together in the suffix array and can be found efficiently with two [[binary search]]es. The first search locates the starting position of the interval, and the second one determines the end position:
{{Citation needed|date=August 2020|reason=Citation needed for the code}}
<syntaxhighlight lang="python">
Line 193 ⟶ 195:
# Find starting position of interval
l = 0 # in Python, arrays are indexed starting at 0
r = n
while l < r:
mid = (l + r) // 2 # division rounding down to nearest integer
Line 204 ⟶ 206:
# Find ending position of interval
r = n
while l < r:
mid = (l + r) // 2
| |||