Упрощенный алгоритм Боуэра-Мура, пара вопросов

[GrishinUS]

Добрый день,

алгоритм записывается с помощью двух предикатов:

1) $P(i,j) = Ak:j<=k<M:s(i-j+k) = pk$
2) $Q(i) = Ak:0<=k<i: NOT P(i,0)$

здесь
p -- искомая подстрока
s -- текст, в котором ищем
M -- длина p

что обозначают символы j и i ?

-- Чт июл 16, 2009 13:23:18 --

модераторов просьба перенести тему в Computer Science
опять я у вас тут запутался...
Надо чаще заглядывать чтоли

-- Чт июл 16, 2009 14:46:12 --

Если предположить что $i$ обозначает индекс первого совпадения в строке $s$
то тогда не совсем понятен смысл $j$

в свете того, что $j<=k< M$, т.е. $j<=M$
а $M$ это длина искомой подстроки.

Если $j$ обозначает количество совпадающих символов, тогда значение $k$ из предиката (1) не будет принимать никакого значения.

Если же $j$ обозначает последний индекс строки $s$ где есть совпадение, то тогда отношение $j<=k< M$ может быть несправедливо для некоторых строк, например для текста

text123456

и искомой подстроки

123

$j = 7$, $M=3$