В зависимости от того, где вы нашли это утверждение, могут быть конкретные причины, по которым оно верно в контексте.
Однако обычная причина для '+ k' состоит в том, что для вставки каждого совпадения, найденного в списке результатов, возвращенном пользователю, требуется O (k) дополнительных операций. Это не обязательно тот случай, когда вместо дерева суффиксов используется инвертированный файл, потому что тогда инвертированный список (он же список публикаций), найденный в индексе , уже является окончательным списком результатов (по крайней мере, если мы предположим, что (а) запрос состоит только из одного токена и (б) инвертированный список сохраняется без сжатия).
Но дерево суффиксов обычно (если оно специально не подготовлено) не содержит таких списков совпадений. Следовательно, во время сопоставления вы определяете путь через дерево, заканчивающийся на каком-то внутреннем узле. Оттуда вы должны следовать всем путям в поддереве этого внутреннего узла, чтобы определить конечные узлы, которые сообщают вам фактические позиции совпадений (один листовой узел на совпадение), и вставить позиции совпадений в список результатов, который вы возвращаете Пользователь. Этот последний шаг - то, что занимает время O (k).
Также обратите внимание, что следование по всем путям в поддереве внутреннего узла, которое вы нашли, может занять значительное дополнительное время, в котором общая сложность даже выше, чем O (n + k). Это зависит от того, есть ли в их поддеревьях прямые указатели от внутренних узлов к конечным узлам.