Самый длинный общий префикс
Урок 10 из 14 курса Префиксные деревья (Trie) — Серия «Структуры данных» №8 на Coddy.
Следующие задачи предназначены для использования в них префиксного дерева (Trie).
Используйте классы Trie и TrieNode, которые вы создали в предыдущих уроках (они предоставлены вам в файлах слева). Каждая задача предоставляет вам новый файл solution, в котором вы пишете функцию, ИСПОЛЬЗУЮЩУЮ Trie.
Наша первая задача: для заданного списка слов найти самый длинный общий префикс, который есть у них всех. После вставки каждого слова в префиксное дерево ответом будет путь от корня вниз до тех пор, пока на каждом шаге существует ровно один дочерний узел и ни один узел не является концом слова (end-of-word).
Задание
ЛегкоНапишите функцию longestCommonPrefix, которая принимает массив строк words и возвращает самую длинную строку, являющуюся префиксом каждого слова в массиве.
Если массив пуст или общего префикса не существует, верните пустую строку.
Вы должны использовать класс Trie (предоставленный в trie вместе с trienode) — не используйте встроенные средства языка, такие как множества, словари или карты для подсчета/отслеживания.
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestCommonPrefix(words, n);
printf("%s\n", res);
free(res);
return 0;
}
Все уроки раздела Префиксные деревья (Trie) — Серия «Структуры данных» №8
3Практические задачи
Самый длинный общий префиксПодсчет слов с префиксомАвтодополнениеСамое длинное слово в словареРазбиение строки на слова