Как решить данную задачу при помощи префиксного дерева?
Задача:
Дан текст. Определить число фрагментов слов, в которых буквы идут по алфавиту.
Тип дерева:
Префиксное дерево
— Такую лабораторную мне дали в университете. Я изучил тему префиксных деревьев и мне не очень ясно, как они могут быть применимы здесь. Как я понял, префиксное дерево просто делает из каждой буквы узел, а также хранит в нём информацию о том, является ли этот узел конечным. То есть само устройство дерева не подразумевает какой-то быстрый подход к решению конкретно этой задачи. Можно конечно просто засунуть все слова из текста в это дерева и каждому узлу присвоить char code, но тогда в чём смысл привлекать к этой задаче деревья, если это можно быстро сделать и без них?
Действительно ли можно как-то это запрограммировать при помощи префиксных деревьев или же тут нужно использовать какое-то другое дерево?
Дополнительное ТЗ:
Составить программу для поиска в линейном (одномерном или многомерном) массиве данных, представленном в виде дерева. В работе использовать следующие виды поиска:
• последовательный;
• бинарный.
Создать дерево (деревья (массив указателей на корни деревьев в случае с многомерной задачей)) поиска (в соответствии с индивидуальным заданием) и заполнить дерево данными из линейного массива данных.
Осуществить поиск данных по дереву. Провести вывод на экран (или файл, по выбору) следующих данных:
• исходного массива данных (матрица или текст в зависимости от варианта);
• значений дерева разными способами (прямой, обратный, центральный обход);
• результатов последовательного и бинарного поиска.
В случае невозможности (из условий индивидуального задания) поиска бинарным методом, провести поиск бинарным методом одной буквы (цифры). Придумать тестовые примеры, для которых были бы эффективными каждый из методов.
Да, действительно, данную задачу можно решить не используя преффексные деревья.
Возможно, вам просто нужно показать умение реализовать и использовать данную структуру данных
Alexandroppolus, честно, это вся информация, но я так полагаю, что условно в тексте «abracadabra lorem ipsum» такими фрагментами будут abr ac ad abr lor ipsu, либо же abr lor ipsu. В целом я считаю что могу себе позволить толковать это как угодно, потом всегда можно будет сослаться на неточность формулировки, препод у нас договороспособный, так что проблем вызвать не должно.
Конечно, на эту задачу можно натянуть префиксные деревья (это же вы бор/trie имеете ввиду, да?). Но тут какая-то растянутая сова получается.
Например, можно, действительно, все слова сложить в trie, а потом его обойти. Вам нужно будет в рекурсивном обходе поддерживать количество последних ребер, которые шли по алфавиту. Еще в каждой вершине сразу хранить, сколько раз через нее проходят добавленные строки. Тогда в каждой вершине прибавляйте к ответу произведение двух счетчиков. При рекурсивном вызове или увеличивайте счетчик последних упорядоченных ребер, если следующий символ больше символа к отцу, или передавайте 1.
Но это нисколько не эффективнее наивного итеративного подхода, где вы это же максимальное количество упорядоченных букв поддерживаете идя по строке слева направо, сбрасывая в 0 на пробелах.
