הקידומת המשותפת הארוכה ביותר
שיעור 10 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.
האתגרים הבאים נועדו להשתמש ב־Trie.
השתמשו במחלקות Trie ו־TrieNode שבניתם בשיעורים הקודמים (הן מסופקות לכם בקבצים שמשמאל). בכל אתגר תקבלו קובץ solution חדש, שבו תכתבו פונקציה שמשתמשת ב־Trie.
הבעיה הראשונה שלנו: בהינתן רשימת מילים, מצאו את הקידומת המשותפת הארוכה ביותר שכולן חולקות. לאחר הכנסת כל מילה לטריי, התשובה היא המסלול מהשורש כלפי מטה, כל עוד יש בדיוק ילד אחד בכל שלב ואף צומת אינו סוף של מילה.
אתגר
קלכתבו פונקציה 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;
}
כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8
3אתגרי תרגול
הקידומת המשותפת הארוכה ביותרספירת מילים עם קידומתהשלמה אוטומטיתהמילה הארוכה ביותר במילוןחלוקת מילהתרגלו בעצמכם: קומפיילר C אונליין