Grapeoff
@Grapeoff
В чём концепция...?

Как решить данную задачу при помощи префиксного дерева?

Задача:
Дан текст. Определить число фрагментов слов, в которых буквы идут по алфавиту.

Тип дерева:
Префиксное дерево

— Такую лабораторную мне дали в университете. Я изучил тему префиксных деревьев и мне не очень ясно, как они могут быть применимы здесь. Как я понял, префиксное дерево просто делает из каждой буквы узел, а также хранит в нём информацию о том, является ли этот узел конечным. То есть само устройство дерева не подразумевает какой-то быстрый подход к решению конкретно этой задачи. Можно конечно просто засунуть все слова из текста в это дерева и каждому узлу присвоить char code, но тогда в чём смысл привлекать к этой задаче деревья, если это можно быстро сделать и без них?

Действительно ли можно как-то это запрограммировать при помощи префиксных деревьев или же тут нужно использовать какое-то другое дерево?

Дополнительное ТЗ:
Составить программу для поиска в линейном (одномерном или многомерном) массиве данных, представленном в виде дерева. В работе использовать следующие виды поиска:
• последовательный;
• бинарный.
Создать дерево (деревья (массив указателей на корни деревьев в случае с многомерной задачей)) поиска (в соответствии с индивидуальным заданием) и заполнить дерево данными из линейного массива данных.
Осуществить поиск данных по дереву. Провести вывод на экран (или файл, по выбору) следующих данных:
• исходного массива данных (матрица или текст в зависимости от варианта);
• значений дерева разными способами (прямой, обратный, центральный обход);
• результатов последовательного и бинарного поиска.
В случае невозможности (из условий индивидуального задания) поиска бинарным методом, провести поиск бинарным методом одной буквы (цифры). Придумать тестовые примеры, для которых были бы эффективными каждый из методов.
  • Вопрос задан
  • 237 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Конечно, на эту задачу можно натянуть префиксные деревья (это же вы бор/trie имеете ввиду, да?). Но тут какая-то растянутая сова получается.

Например, можно, действительно, все слова сложить в trie, а потом его обойти. Вам нужно будет в рекурсивном обходе поддерживать количество последних ребер, которые шли по алфавиту. Еще в каждой вершине сразу хранить, сколько раз через нее проходят добавленные строки. Тогда в каждой вершине прибавляйте к ответу произведение двух счетчиков. При рекурсивном вызове или увеличивайте счетчик последних упорядоченных ребер, если следующий символ больше символа к отцу, или передавайте 1.

Но это нисколько не эффективнее наивного итеративного подхода, где вы это же максимальное количество упорядоченных букв поддерживаете идя по строке слева направо, сбрасывая в 0 на пробелах.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы