Почему сложность вхождения в дереве суффиксов равна O (mn)?

Question

На основании этого http://www.itu.dk/courses/AVA/E2005/StringIndexing.pdf на стр. 12/36

Учитывая строку T [1 ... n] , мы строим дерево суффиксов.Шаблон поиска: P [1 ... m] .

• Preprocessing: O(n^2)
• Space: O(n^2)
• Occur(P in suffix tree): O(n*m) <===== why?
• Member is: O(m)

Answer 1

Операция Occur (...) в материале, на который вы ссылаетесь, связана не с поиском P из дерева суффиксов, а с поиском самых длинных совпадений (т. Е. Найдите самую длинную подстроку P, которая встречается в дереве поиска) и отчетом. соответствующие листья. Это наихудший случай операции O (nm), потому что вам нужно брать каждый суффикс P (это O (m)) и, возможно, сообщать, что O (n) удаляется каждый раз.