ספירת מופעי תת-סדרה במחרוזת

נתונות מחרוזת תווים str ומחרוזת תווים pattern.

יש להחזיר את מספר הפעמים שמחרוזת pattern מופיעה בתוך המחרוזת str כתת-סדרה. שימו לב שהמחרוזת pattern לא צריכה להופיע ברציפות בתוך str.

לדוגמא,

אם המחרוזת str = "subsequence" והמחרוזת pattern = "sue"

אז יוחזר 7 שכן המחרוזת "sue" נמצאת 7 פעמים כתת-סדרה במחרוזת "subsequence"

כמפורט להלן:

1. subsequence
2. subsequence  
3. subsequence
4. subsequence
5. subsequence
6. subsequence
7. subsequence

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

אילוצים:
  • שיטות מהמחלקה String המותרות לשימוש:
    • public char charAt(int i) - המחזירה את התו במקום ה-i במחרוזת.
    • public int length() - המחזירה את אורך המחרוזת.
דוגמה 1:
קלט: 
str = "subsequence",
pattern = "sue"
פלט: 
7

הסבר: המחרוזת "sue" מופיעה 7 פעמים כתת-סדרה במחרוזת "subsequence".

דוגמה 2:
קלט: 
str = "abc",
pattern = "abc"
פלט: 
1

הסבר: המחרוזת "abc" מופיעה פעם אחת כתת-סדרה במחרוזת "abc".

דוגמה 3:
קלט: 
str = "abc",
pattern = "xyz"
פלט: 
0

הסבר: המחרוזת "xyz" לא מופיעה כתת-סדרה במחרוזת "abc".

דוגמה 4:
קלט: 
str = "hello",
pattern = ""
פלט: 
1

הסבר: מחרוזת ריקה מופיעה פעם אחת כתת-סדרה בכל מחרוזת.

דוגמה 5:
קלט: 
str = "aabb",
pattern = "ab"
פלט: 
4

הסבר: המחרוזת "ab" מופיעה 4 פעמים כתת-סדרה במחרוזת "aabb".

דוגמה 6:
קלט: 
str = "aaaa",
pattern = "aa"
פלט: 
6

הסבר: המחרוזת "aa" מופיעה 6 פעמים כתת-סדרה במחרוזת "aaaa".

דוגמה 7:
קלט: 
str = "abaca",
pattern = "a"
פלט: 
3

הסבר: התו 'a' מופיע 4 פעמים במחרוזת "abaca".

דוגמה 8:
קלט: 
str = "",
pattern = "a"
פלט: 
0

הסבר: אם המחרוזת הראשית ריקה והתבנית לא ריקה, התוצאה היא 0.

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

קלט:

str = "subsequence",
pattern = "sue"

הפלט המבוקש:

7