ספירת מילים עם קידומת
שיעור 11 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 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;
}
כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8
3אתגרי תרגול
הקידומת המשותפת הארוכה ביותרספירת מילים עם קידומתהשלמה אוטומטיתהמילה הארוכה ביותר במילוןחלוקת מילהתרגלו בעצמכם: קומפיילר C אונליין