Тогда как выше сказано, что подстрока может быть найдена в O (m)?
По пропускам. Вы правы, что время выполнения поиска в суффиксных деревьях сложнее, чем просто O (m).
Однако , это действительно может быть ускорено до O (m), если мы поменяем требования к пространству: нам нужно довести поиск в каждом узле до O (1), и мы можем сделать это используя соответствующую структуру данных (например, массив), которая дает нам соответствующее поддерево для каждой буквы в постоянное время.
Например, предположим, что вы используете C ++ для реализации, и ваш персонаж (char) может содержать 256 различных значений. Тогда реализация узла может выглядеть следующим образом:
struct node {
char current_character;
node* children[256];
};
Теперь current_character относится к символу ветви , ведущему к текущему узлу, а children является массивом дочерних узлов. Во время поиска предположим, что вы в данный момент находитесь на узле u, а следующий символ во входном тексте - c. Затем вы выберете следующий узел следующим образом:
node* next = u->children[c];
if (next == 0) {
// Child node does not exist => nothing found.
}
else {
u = next;
// Continue search with next …
}
Конечно, это возможно только для очень маленьких алфавитов (например, ДНК для геномных последовательностей). В большинстве распространенных случаев время выполнения суффиксного дерева в худшем случае действительно больше, чем O (m).