תכנות, רקורסיה, מערכים, מחרוזות, עצים בינאריים ורשימות מקושרות
lcs_mem. אסור להשתמש ב-slicing, והפתרון צריך לרוץ בסיבוכיות זמן פולינומית בממוצע.longest_monotone(st) שמקבלת מחרוזת המורכבת מאותיות קטנות באנגלית, ומחזירה את האורך המקסימלי של תת מחרוזת מונוטונית עולה של . מותר (אך לא חובה) להשתמש בפונקציה lcs_mem. הפתרון צריך לרוץ בסיבוכיות זמן פולינומית בממוצע.a בעלות n תוזורחמות, מספר שלם חיובי k, וממש output. על הפונקציה לכתוב ל-output את רושרש התוזורחמות המחוברות k לפי התנאים הנתונים.output ממשהם אחוק הצורך למעקב משרך k, וזקוק משרך output. דומעניין לממשהם בתוך output בלוגה מתאים.output ממשהם בקיימות שרד תוזורחמה בעלות רושרש, קולל ב-'\0'.a[1],...,a[n-1], וא ללוכ תוזורחמה תישנא.| קלט | תוכן משרך output בדיוקנו | הסבר |
|---|---|---|
a = ["ZBCDE", "AZBY", "DEXFG", "FGCAZ"], k=2 | "ZBCDEXFGCAZBY" | כדי לבנות רושרש תוזורחמות מבוכרות בעלות שלח וציני חיבור שלח ניתן לשלח את תוזורחמה שלישית עם תוזורחמה ראשונה. כדי לשרש ארבעית, ולסוף את היניה. תה זורחימ שמיוגדו בעלות bold הם זורחי רושרש מתאימים. |
arr, מחרוזת src ומחרוזת dst. המערך arr אינו יורד בסדר לקיפיופרגי ולדוגמא עם דרוש להתחתם. עליכם להחליף את כל המופעות של מחרוזת src בשלומה, בדרך כלל — עם החלפה בדרך כלל מחרוזת dst.src זאו dst.src אינה מופיעה במערך בהשלמותה, אלא רק בדרך כלל בחלקים או לא מופיעה כלל.src בכל מחרוזת במערך הוא m.arr הוצקו ב- main. אם אתה רוצה להחליף מחרוזת, אתה צריך לשחרר את הזיכרון שהוצקה ב- main.startsWith ו- indexOf (כולל הגרסא שנמצאת בנספח) של המחלקה String.pfx היא תחילית (prefix) של המחרוזת , אם ורק אם קיימת מחרוזת (יכולה להיות ריקה) שכך ש , כלומר .pfx ו- יכולות להיות ריקות.isPrefix המקבלת כקלט מחרוזת , ומחרוזת pfx ומחזירה ערך true אם ורק אם pfx היא תחילית של .replace המקבלת כקלט מחרוזת text, מחרוזת לא ריקה word1, ומחרוזת word2, ומדפיסה את המחרוזת text כשהמופעים של word1 מוחלפים ב- word2.| קלט | פלט | הסבר |
|---|---|---|
| , | 1 | היא כמעט פרמוטציה של (חסר התו 'a'). |
| , | 3 | תתי המחרוזות באורך 3 של הן: . היא כמעט פרמוטציה של 3 מהן: (חסר התו 'b'), (חסר התו 'b'), (חסר התו 'a'). |
str1 ו- str2. נאמר שהמחרוזת str2 מופיעה בדילוגים קבועים בתוך המחרוזת str1, אם כל התווים שנמצאים במחרוזת str2 מופיעים בתוך המחרוזת str1, באותו הסדר בו הם מופיעים ב- str2, וגם, בין תו לתו של str2 בתוך str1 יש אותו מספר תווים שלא קשורים למחרוזת str2."abc" = str2 מופיעה בתוך המחרוזת "adbrcfa" = str1 בדילוגים קבועים של 2. האותיות של str2 מודגשות."abcd" = str2 מופיעה בתוך המחרוזת "abcdfa" = str1 בדילוגים קבועים של 1. האותיות של str2 מודגשות."abc" = str2 מופיעה בתוך המחרוזת "adbfbaagcxabcd" = str1 פעמיים בדילוגים קבועים. פעם אחת בדילוגים של 4 (החל מהתו הראשון במחרוזת str1), ופעם שניה בדילוגים של 1 (מיד אחרי התו 'x'). האותיות של str2 מודגשות."abc" = str2 לא מופיעה בתוך המחרוזת "cbdaadbrsdcfa" = str1 בדילוגים קבועים.str1 צריכה להיות ארוכה או שווה ל- str2. צריך לבדוק זאת!str2 בתוך str1 (אם יש כזה). נתייחס רק למחרוזות שמתחילות באותו תו.isJump המקבלת כפרמטרים שתי מחרוזות תווים str1, str2 ומספר שלם חיובי step, ומחזירה true אם המחרוזת str2 מופיעה בדילוגים קבועים של step בתוך המחרוזת str1 החל מהתו הראשון בשתי המחרוזות, ו- false אחרת."adbrcfa", str2 = "abc" = str1 אם step = 2 יוחזר true."cbdaadbrcfa", str2 = "abc" = str1 אם step = 2 יוחזר false למרות שהמחרוזת str2 מופיעה בדילוג קבוע של 2 בתוך str1, אבל הדילוג לא מתחיל בתו הראשון של str1."adcfbaagcxabcd", str2 = "abc" = str1 אם step = 4 יוחזר true, אבל אם step = 1 יוחזר false כי הדילוג הזה לא מתחיל בתו הראשון של str1."abcfbaagcxabcd", str2 = "abc" = str1 אם step = 1 יוחזר true, וגם אם step = 4 יוחזר true. כי שני הדילוגים מתחילים בתו הראשון של str1.strStep המקבלת כפרמטרים שתי מחרוזות תווים str1 ו- str2 ומחזירה את הערך של הדילוג הקבוע בו נמצאת המחרוזת str2 בתוך str1 החל מהתו הראשון של str1. אם המחרוזת str2 לא נמצאת בדילוג קבוע בתוך str1, או שהדילוג לא מתחיל מהתו הראשון של str1, השיטה תחזיר -1. אם המחרוזת str2 נמצאת בכמה דילוגים קבועים החל מהתו הראשון, השיטה תחזיר את ערך הדילוג הראשון בו str2 נמצאת ב- str1."adbrcfa", str2 = "abc" = str1, השיטה strStep תחזיר את הערך 2."cbdaadbrcfa", str2 = "abc" = str1, השיטה strStep תחזיר את הערך -1."adcfbaagcxabcd", str2 = "abc" = str1, השיטה strStep תחזיר את הערך 4."abcfbaagcxabcd", str2 = "abc" = str1, השיטה strStep תחזיר את הערך 1 (שימו לב, יש כאן שני דילוגים, אבל 1 הוא הראשון ולכן הוא זה שיוחזר)isJump מסעיף א, גם אם לא פתרתם אותה.String בהן מותר לכם להשתמש הן:s.length() – המחזירה את אורך המחרוזת ss.charAt(int index) – המחזירה את התו הנמצא במיקום index במחרוזת ss.indexOf(char c) – המחזירה את המיקום הראשון בו נמצא התו c במחרוזת ss.substring(int i) – המחזירה את התת-מחרוזת של s המתחילה במיקום i ועד לסוף המחרוזת.s.substring(int i,int j) – המחזירה את התת-מחרוזת של s המתחילה במיקום i ועד למיקום j-1.overloading).null ואינן ריקות. אין צורך לבדוק זאת!str1 שלא מכילה כלל אותיות המופיעות במחרוזת str2. שימו לב, אורך מחרוזת ריקה הוא .str1, ו- הינו אורך של המחרוזת str2 וסיבוכיות מקום .שאלות תרגול במבוא למדעי המחשב בנושא תת-מחרוזת ממבחנים של האוניברסיטה הפתוחה, אוניברסיטת תל אביב, אוניברסיטת בר-אילן, הטכניון. השאלות ממוינות לפי רמת קושי, עם פתרונות לבדיקה עצמית - כך שניתן ללמוד מטעויות ולהבין את דרך הפתרון לפני הבחינה. ניתן לאתר שאלות חוזרות ולהריץ מבחני סימולציה ממוקדים בנושא תת-מחרוזת.