Для любой вершины v дерева K определим lp(v) как длину наибольшего собственного суффикса строки L(v), которая является префиксом некоторого образца из P.

Для вершины v дерева K пусть nv — единственная вершина в K, помеченная суффиксом L(v) длины lp(v). Если lp(v) = О, то nv — корень K.

Предположим, что мы знаем связь неудачи v - nv для каждой вершины v из K.

Например, рассмотрим текст t = xxpotattooxx и дерево ключей. Когда / = 3, текст совпадает со строкой potat, а в следующем

символе — уже несовпадение. В этой точке с = 8, связь неудачи от вершины i>,

помеченной строкой potat, указывает на вершину nVi помеченную tat, и lp(v) = 3.

Таким образом, l возрастает до 5 = 8 - 3, и следующее сравнение будет между сим-

волом Г(8) и символом t на дуге ниже tat.

В этом алгоритме, когда дальнейшие совпадения уже невозможны, l может воз-

расти больше чем на единицу, избавляя тем самым от повторной проверки символы

из Т слева от с, и при этом мы сохраняем уверенность, что каждое вхождение об-