1 Тема от alexeigor Отредактировано alexeigor (2010-10-28 22:36:43)

  • alexeigor
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-10-14
  • Сообщений: 2

Тема: Хэш подстроки и его быстрое вычисление

В статье http://e-maxx.ru/algo/string_hashes написано следующее:
----
Предположим, нам дана строка S, и даны индексы I и J. Требуется найти хэш от подстроки S[I..J].

По определению имеем:

H[I..J]  =  S[i]  +  S[I+1] * P  +  S[I+2] * P^2  +  ...  + S[J] * P^(J-I)

откуда:

H[I..J] * P[i]  =  S[i] * P[i]  +  ...  +  S[J] * P[J],
H[I..J] * P[i]  =  H[0..J]  -  H[0..I-1]

----

случайно в строке 

H[I..J] * P[i]  =  S[i] * P[i]  +  ...  +  S[J] * P[J]

нет ошибки? может должно быть 

S[J]*P[i]

?

также лучше пояcнить что за массив P

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Хэш подстроки и его быстрое вычисление

Вроде всё правильно. Массив P - содержит все степени заданного числа-основания хеша (P[ i ] - это константа P в степени i).

Речь там о том, что если мы подсчитаем хеши от всех префиксов H[ i ], то разность двух таких префиксных хешей H[ j ] - H[ i-1 ] даст хеш от подстроки S[i..j], но умноженный на P в степени i.

Сайтe-maxx