Подсчет слов с префиксом
Урок 11 из 14 курса Префиксные деревья (Trie) — Серия «Структуры данных» №8 на Coddy.
Сколько сохраненных слов начинаются с данного префикса? После вставки каждого слова пройдите от корня по одному символу за раз вдоль префикса. Если какой-либо символ отсутствует, ответ — ноль: ни одно слово не может начинаться с этого префикса.
Если вы дойдете до конца префикса, вы окажетесь в узле. Каждое сохраненное слово, начинающееся с этого префикса, находится где-то в поддереве с корнем в этом узле. Подсчитайте их, обходя поддерево и прибавляя 1 для каждого узла, где isEndOfWord имеет значение true.
Задание
ЛегкоНапишите функцию countWordsWithPrefix, которая принимает массив строк words и строку prefix и возвращает количество слов в массиве, начинающихся с данного префикса.
Пустой префикс соответствует каждому слову.
Вы должны использовать класс Trie (предоставленный в trie вместе с trienode) — не используйте встроенные средства языка, такие как множества (sets), словари (dicts) или карты (maps) для подсчета или отслеживания.
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
return 0;
}
Все уроки раздела Префиксные деревья (Trie) — Серия «Структуры данных» №8
3Практические задачи
Самый длинный общий префиксПодсчет слов с префиксомАвтодополнениеСамое длинное слово в словареРазбиение строки на слова