מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תת-מחרוזת משותפת ארוכה ביותר/שאלה

הגדרה: מחרוזת היא רצף של תווים. אם $\displaystyle X=x_{1}\ldots x_{m}$,‏ $\displaystyle Y=y_{1}\ldots y_{n}$,‏ ו$\displaystyle Z=z_{1}\ldots z_{k}$ הן שלוש מחרוזות, אז: $\displaystyle Z$ היא תת-מחרוזת של $\displaystyle X$ אם קיימת סדרה עולה ממש של אינדקסים $\displaystyle i_{1},\ldots ,i_{k}$ כך ש$\displaystyle x_{i_{j}}=z_{j}$ לכל $\displaystyle j$. $\displaystyle Z$ היא תת-מחרוזת משותפת של $\displaystyle X$ ו$\displaystyle Y$ אם היא תת-מחרוזת הן של $\displaystyle X$ והן של $\displaystyle Y$

דוגמה: $\displaystyle Hello$ ו$\displaystyle ABCBDAB$ הן מחרוזות. אם $\displaystyle X=ABCBDAB$ ו$\displaystyle Y=BDCABA$, אז: אם נקבע $\displaystyle Z=BCBA$, אז $\displaystyle Z$ היא תת-מחרוזת של $\displaystyle X$. גם אם נקבע $\displaystyle Z=ABCBDAB$ (כלומר $\displaystyle X$ עצמה), אז $\displaystyle Z$ היא תת-מחרוזת של $\displaystyle X$. אם $\displaystyle X=ABCBDAB$ ו$\displaystyle Y=BDCABA$, אז $\displaystyle Z=BCBA$ היא תת-מחרוזת משותפת ל$\displaystyle X$ ול$\displaystyle Y$ (מבין כמה תתי-מחרוזות אפשריות).

הגדרה: אם $\displaystyle X$ ו$\displaystyle Y$ הן מחרוזות, אז $\displaystyle Z$ היא הLCS (או longest common subsequence), אם היא הארוכה ביותר מבין תתי-המחרוזות המשותפות ל$\displaystyle X$ ול$\displaystyle Y$.

בשאלה זו עליך למצוא אלגוריתם יעיל למציאת הLCS לכל שתי מחרוזות $\displaystyle X$ ו$\displaystyle Y$:

1. אנא תאר אלגוריתם יעיל המוצא את אורך הLCS.
2. אנא תאר אלגוריתם יעיל המדפיס את הLCS עצמו.

שימו לב: בכל אחד משני הסעיפים: הנח שX וY הם שני מערכים גלובליים המתארים את המחרוזות $\displaystyle X$ ו$\displaystyle Y$, בעלות האורכים $\displaystyle m$ ו$\displaystyle n$ בהתאמה. אנא הוכח נכונות תשובתך, ונתח את סיבוכיותה במונחי $\displaystyle m$ ו$\displaystyle n$.