תת-סדרה משותפת ארוכה ביותר של שלוש מחרוזות

בהינתן מחרוזת תווים st, נגדיר תת-סדרה (sequence-sub) של המחרוזת כמחרוזת שנשארה לאחר שהורדו ממנה חלק מהתווים.

למשל, אם המחרוזת המקורית st = "abcde" אז כל אחת מהמחרוזות להלן היא תת-סדרה של st (לא כתבנו כאן את כל האפשרויות):

"ab", "ce", "acd", "d", "abcde", "" (המחרוזת הריקה)

שימו לב, תת-סדרה (sequence-sub) אינה תת-מחרוזת (string-sub), ולכן התווים אינם צריכים להיות במיקום עוקב דווקא, אבל הסדר ביניהם צריך להיות כמו הסדר במחרוזת המקורית, ולא יכולים להיות תווים שלא היו במחרוזת המקורית.

לכן, המחרוזות להלן אינן תת-סדרה של st:

"ba", "cf", "edcba", "g"

בהינתן שלוש מחרוזות תווים st1, st2, st3, נגדיר את התת-סדרה המשותפת הארוכה ביותר לשלוש המחרוזות, כמחרוזת תווים הארוכה ביותר שאפשר ליצור כאשר מורידים חלק מהתווים מכל אחת מהמחרוזות.

יש להחזיר את האורך של המחרוזת שמהווה תת-סדרה משותפת אורכה ביותר של שלוש המחרוזות. אם אין תת-סדרה כזו יוחזר 0.

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

דוגמה 1:
קלט: 
st1 = "ABCBDAB",
st2 = "BDCABA",
st3 = "BADACB"
פלט: 
4

הסבר: התת-סדרה הארוכה ביותר המשותפת היא "BDAB"

דוגמה 2:
קלט: 
st1 = "ABCBDAB",
st2 = "XYZ",
st3 = "DC"
פלט: 
0

הסבר: רק המחרוזת הריקה משותפת לשלוש המחרוזות

דוגמה 3:
קלט: 
st1 = "ABC",
st2 = "ABC",
st3 = "ABC"
פלט: 
3

הסבר: כל המחרוזות זהות, ולכן התת-סדרה המשותפת היא המחרוזת המלאה "ABC"

דוגמה 4:
קלט: 
st1 = "AAAA",
st2 = "AAA",
st3 = "AA"
פלט: 
2

הסבר: התת-סדרה המשותפת הארוכה ביותר היא "AA"

דוגמה 5:
קלט: 
st1 = "A",
st2 = "A",
st3 = "A"
פלט: 
1

הסבר: מחרוזת באורך 1 המשותפת לכולן

דוגמה 6:
קלט: 
st1 = "",
st2 = "ABC",
st3 = "DEF"
פלט: 
0

הסבר: אחת המחרוזות ריקה, ולכן רק המחרוזת הריקה משותפת

דוגמה 7:
קלט: 
st1 = "ABCDEF",
st2 = "ACDEF",
st3 = "ABDEF"
פלט: 
4

הסבר: התת-סדרה המשותפת הארוכה ביותר היא "ADEF"

דוגמה 8:
קלט: 
st1 = "ABC",
st2 = "BAC",
st3 = "CAB"
פלט: 
1

הסבר: מחרוזת באורך 1 המשותפת לכולן

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

קלט:

st1 = "ABCBDAB",
st2 = "BDCABA",
st3 = "BADACB"

הפלט המבוקש:

4