130
правок
Изменения
Индексация с нуля
}}
{{Определение
|definition = Будем говорить, что строка <tex>z[1 0 \,\mathinner{\ldotp\ldotp} \, m-1]</tex> является подстрокой строки <tex>s[1 0 \,\mathinner{\ldotp\ldotp} \, n-1]</tex>, если существует такой индекс <tex>k \in [0\, \mathinner{\ldotp\ldotp}\, n - m]</tex>, что для любого <tex>i \in [1 0 \,\mathinner{\ldotp\ldotp} \, m-1]</tex> справедливо <tex>s[k + i] = z[i]</tex>.
}}
<tex>f(i)</tex> — предикат, описанный в алгоритме.
'''bool''' f(i: '''int'''):
hashes = хеши подстрок строки <tex>s</tex> длины <tex>i</tex>
'''for''' j = 1 0 '''to''' |t| − i + 1
hash = hash(t[j .. j + i − 1])
'''if''' hash '''in''' hashes
