מציאת דילוג קבוע במחרוזת

בהינתן שתי מחרוזות תווים str1 ו- str2, המתחילות באותו התו נאמר שהמחרוזת str2 מופיעה בדילוגים קבועים במחרוזת str1, אם כל התווים שנמצאים במחרוזת str2 מופיעים בתוך המחרוזת str1, באותו הסדר בו הם מופיעים ב- str2, וגם, בין תו לתו של str2 בתוך str1 יש אותו מספר תווים שלא קשורים למחרוזת str2.

לדוגמה,

  1. המחרוזת str2 = "abc" מופיעה בתוך המחרוזת str1 = "adbrcfa" בדילוגים קבועים של 2.
  2. המחרוזת str2 = "abcd" מופיעה בתוך המחרוזת str1 = "abcdfa" בדילוגים קבועים של 1.
  3. המחרוזת str2 = "abc" מופיעה בתוך המחרוזת str1 = "adbfbaagcxabcd" בדילוגים כפולים. פעם אחת בדילוגים של 4 (החל מהתו הראשון במחרוזת str1), ופעם שנייה בדילוגים של 1 (מיד אחרי התו x).
  4. המחרוזת str2 = "abc" לא מופיעה בתוך המחרוזת str1 = "cbdaadbrsdcfa" בדילוגים קבועים.

שימו לב, ברור ש- str1 צריכה להיות ארוכה או שווה ל- str2. צריך לבדוק זאת!

 

כתבו שתי שיטות רקורסיביות:

  • isJump המקבלת כפרמטרים שתי מחרוזות תווים str1, str2 ומספר חיובי step, ומחזירה true אם המחרוזת str2 מופיעה בדילוגים קבועים בתוך המחרוזת str1 כאשר הדילוג קבוע של step תווים, ו- false אחרת.

לדוגמה,

  1. אם str1 = "adbrcfa", str2 = "abc" אז step = 2 ויוחזר true.
  2. אם str1 = "cbdadbrcfa", str2 = "abc" בדילוג קבוע של 2 יוחזר false, כי הדילוג לא מתחיל בתו הראשון של str1.
  3. אם str1 = "adcfbaagcxabcd", str2 = "abc" אז step = 4 יוחזר true, אבל אם step = 1 יוחזר false כי הדילוג הזה לא מתחיל בתו הראשון של str1.
  4. אם str1 = "abcfbaagcxabcd", str2 = "abc" אז step = 1 יוחזר true, וגם אם step = 4 יוחזר true. כי שני הדילוגים מתחילים בתו הראשון של str1.

 

  • strStep המקבלת כפרמטרים שתי מחרוזות תווים str1 ו-str2 ומחזירה את הערך של הדילוג הקבוע בו נמצאת המחרוזת str2 בתוך str1. החל מהתו הראשון של str1. אם המחרוזת str2 לא נמצאת בדילוג קבוע בתוך str1, או שהדילוג לא מתחיל מהתו הראשון של str1, יוחזר -1. אם המחרוזת str2 נמצאת בכמה דילוגים קבועים החל מהתו הראשון, השיטה תחזיר את ערך הדילוג הראשון בו נמצאת str2 ב-str1.

לדוגמה,

  1. str1 = "adbrcfa", str2 = "abc, יוחזר הערך 2.
  2. str1 = "cbdadbrcfa", str2 = "abc, יוחזר הערך  -1.
  3. str1 = "adcfbaagcxabcd", str2 = "abc, יוחזר הערך 4.
  4. str1 = "abcfbaagcxabcd", str2 = "abc, יוחזר הערך 1. (שימו לב, יש כאן שני דילוגים, אבל 1 הוא הראשון ולכן הוא זה שיוחזר).

שימו לב, יש להשתמש בשיטה isJump.

השיטות צריכות להיות רקורסיביות ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:

  • שיטות מהמחלקה String המותרות לשימוש:

    • s.length() - המחזירה את אורך המחרוזת s.
    • s.charAt(int index) - המחזירה את התו הנמצא במיקום index במחרוזת s.
    • s.indexOf(char c) - המחזירה את המיקום הראשון בו נמצא התו c במחרוזת s.
    • s.substring(int i) - המחזירה את תת-המחרוזת של s המתחילה במיקום i ועד לסוף המחרוזת.
    • s.substring(int i,int j) - המחזירה את תת-המחרוזת של s המתחילה במיקום i ועד למיקום j-1 (כולל).
  • המחרוזות אינן null ואינן ריקות.
דוגמה 1:
קלט: 
str1 = "adbrcfa",
str2 = "abc"
פלט: 
2

הסבר: הדילוג הקבוע בו נמצאת המחרוזת "abc" בתוך "adbrcfa" הוא 2.

דוגמה 2:
קלט: 
str1 = "cbdadbrcfa",
str2 = "abc"
פלט: 
-1

הסבר: המחרוזת "abc" לא נמצאת בדילוג קבוע בתוך "cbdadbrcfa".

דוגמה 3:
קלט: 
str1 = "adcfbaagcxabcd",
str2 = "abc"
פלט: 
4

הסבר: הדילוג הקבוע בו נמצאת המחרוזת "abc" בתוך "adcfbaagcxabcd" הוא 4.

דוגמה 4:
קלט: 
str1 = "abcfbaagcxabcd",
str2 = "abc"
פלט: 
1

הסבר: ישנם שני דילוגים בהם נמצאת המחרוזת "abc", אך הראשון הוא 4 ולכן הוא זה שיוחזר.

דוגמה 5:
קלט: 
str1 = "abcdefgh",
str2 = "ace"
פלט: 
2

הסבר: הדילוג הקבוע בו נמצאת המחרוזת "ace" בתוך "abcdefgh" הוא 1.

Loading...
נשמרLn 1, Col 1

קלט:

str1 = "adbrcfa",
str2 = "abc"

הפלט המבוקש:

2