Menu
Coddy logo textTech

הקידומת המשותפת הארוכה ביותר

שיעור 10 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.

האתגרים הבאים נועדו להשתמש ב־Trie.

השתמשו במחלקות Trie ו־TrieNode שבניתם בשיעורים הקודמים (הן מסופקות לכם בקבצים שמשמאל). בכל אתגר תקבלו קובץ solution חדש, שבו תכתבו פונקציה שמשתמשת ב־Trie.

הבעיה הראשונה שלנו: בהינתן רשימת מילים, מצאו את הקידומת המשותפת הארוכה ביותר שכולן חולקות. לאחר הכנסת כל מילה לטריי, התשובה היא המסלול מהשורש כלפי מטה, כל עוד יש בדיוק ילד אחד בכל שלב ואף צומת אינו סוף של מילה.

challenge icon

אתגר

קל

כתבו פונקציה 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

תרגלו בעצמכם: קומפיילר C אונליין