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

המבנה הרקורסיבי של הבעיה

ראשית מספר סימונים:

1. כפי שצוין בשאלה, נגדיר את אורך $X$ כ$m$, ואת אורך $Y$ כ$n$.
2. נסמן את הרישה ה$i$ של מחרוזת $X$ כ$X_i$. במילים אחרות, $X_i=x_1,\mathrm{...},x_i$.‏
3. נגדיר כ$l(i,j)$ את אורך הLCS של $X_i$ ו$Y_j$. במילים אחרות, $l(i,j)$ היא אורך תת-הסדרה הארוכה ביותר המשותפת ל$X_i$ ו$Y_j$.

עכשיו תורכם: וודא שהמך מבין מדוע לפי הגדרה זו, $l(m,n)$ הוא אורך הLCS של $X$ ו$Y$.

משפט: $l(i,j)$ מקיים את הנוסחה הבאה: אם $i=0$ או $j=0$,‏ אז $l(i,j)=0$. אם לא,‏ אז: אם $x_i=y_j$, אז $l(i,j)=1+l(i-1,j-1)$. אם $x_i\ne y_j$, אז $l(i,j)=max\{l(i-1,j),l(i,j-1)\}$.

הוכחה: אם $i=0$ או $j=0$, אז (לפחות) אחת המחרוזות היא המחרוזת הריקה, ורק המחרוזת הריקה יכולה להיות תת-מחרוזת של המחרוזת הריקה. למחרוזת הריקה יש אורך 0, ומכאן החלק הראשון של המשפט.

מכאן נניח ששתי המחרוזות אינן ריקות.

נניח ש$x_i=y_j$. ראשית, קל לראות שבהכרח תווה האחרון של $Z$ הוא $x_i$ - אם זה לא היה המצב, אז $Z{x}_i$ גם היא מחרוזת משותפת ל$X_i$ ו$Y_j$, דבר שנוגד עפ"י ההגדרה את היותה של $Z$ תת-המחרוזת המשותפת הארוכה ביותר. נחשוב כעת על כל תתי המחרוזות המשותפות מהצורה $Z^{\prime }{x}_i$: עבור כל אחת מהן, קל לראות ש$Z^{\prime }$ היא תת-מחרוזת משותפת ל$X_{i-1}$ ו$Y_{j-1}$, ולכן בהכרח הארוכה שבהן היא זו שהרישה שלה היא הLCS של $X_{i-1}$ ו$Y_{j-1}$.

לחלופין, נניח ש$x_i\ne y_j$; יש שלוש אפשרויות:

1. $Z$מסתיימת ב$x_i$ - אם כן, הLCS בהכרח מהצורה $Z^{\prime }{x}_i$, כאשר $Z^{\prime }$ היא הLCS של $X_i$ ו$Y_{j-1}$.
2. $Z$ מסתיימת ב$y_j$ - אם כן, הLCS בהכרח מהצורה $Z^{\prime }{y}_j$, כאשר $Z^{\prime }$ היא הLCS של $X_{i-1}$ ו$Y_j$.
3. $Z$אינה מסתיימת ב$x_i$, וכן אינה מסתיימת ב$y_j$ - אם זה המצב, אז הLCS של $X_{i-1}$ ו$Y_{j-1}$ הוא הLCS של $X_{i-1}$ ו$Y_j$ (וכן גם הLCS של $X_i$ ו$Y_{j-1}$), כך ששתי הבדיקות הקודמות מכסות כבר (פעמיים אפילו) מקרה זה.

מציאת אורך הLCS

להלן פסוודו-קוד למציאת אורך הLCS.

1	L = Make-Matrix(m, n)

2	for i in [1, ..., m]
3		for j in [1, ..., n]
4			L[i][j] = Nil

LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6		else
7			guess-x = LCS-Length(i - 1, j)
8			guess-y = LCS-Length(i, j - 1)
		
9			L[i][j] = Max(guess-x, guess-y)

10	return L[i][j]

ארבע השורות הראשונות מאתחלות מטריצה המשמשת לmemoization, והפונקציה LCS-Length מוצאת את את האורך המבוקש. 1-4 מייצרות מטריצה (גלובלית) שכל אחד מאיבריה מאותחל לNil.‏ 2-9 של LCS-Length, פועלות בדיוק לפי נוסחת הנסיגה הקודמת (שאת נכונותה כבר הראינו). המטריצה L, בפרט ב1 של LCS-Length, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה בעבר.

ניתוח סיבוכיות

נגדיר את $T^{\prime }(i,j)$ כזמן שאורכת LCS-Length בהנחה שכל אחת מקריאותיה הרקורסיביות היא $O(1)$. קל לראות ש$T^{\prime }(i,j)=O(1)$.

זמן הריצה של LCS-Length(m, n) חסום מלמעלה על ידי $\sum _{i=0}^m\sum _{j=0}^n[T^{\prime }(i,j)]=\mathrm{\Theta }(m\cdot n)$. חוץ מכך ישנו האתחול 1-4 שאורך גם כן $\mathrm{\Theta }(m\cdot n)$. הזמן הכולל, לכן, הוא $O(m\cdot n)$.

הדפסת איברי הLCS

ראשית נשנה מעט את הפסוודו-קוד הקודם.

1	L = Make-Matrix(m, n)
2	D = Make-Matrix(m, n)

3	for i in [1, ..., m]
4		for j in [1, ..., n]
5			L[i][j] = Nil


LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6			D[i][j] = 'b'
7		else
8			guess-x = LCS-Length(i - 1, j)
9			guess-y = LCS-Length(i, j - 1)
		
10			L[i][j] = Max(guess-x, guess-y)
	
11			if L[i][j] == guess-x
12				D[i][j] = 'x'
13			else
14				D[i][j] = 'y'	

15	return L[i][j]

המטריצה הגלובלית D מתארת בכניסה ה$(i,j)$ את ההחלטה לגבי הLCS של $X_i$ ו$Y_j$:

1. 'x' מסמלת את ההחלטה לוותר על התו האחרון ב$X_i$.
2. 'y' מסמלת את ההחלטה לוותר על התו האחרון ב$Y_j$.
3. 'b' מסמלת את ההחלטה לוותר על התו האחרון בשניהם. זה בדיוק המצב בו $X_i=Y_j$ נמצא כחלק מהLCS.הפונקציה הבאה מדפיסה את הLCS כאשר קוראים לPrint-LCS(m, n):

Print-LCS(i, j)
1	if i > 1 and j > 1
2		if D[i][j] == 'x':
3			Print-LCS(i - 1, j)
4		else if D[i][j] == 'y':
5			Print-LCS(i, j - 1)
6		else
7			Print-LCS(i - 1, j - 1)

1	if D[i][j] == 'b':
2		Print(X[i])

קל לראות שהסיבוכיות עדיין $\mathrm{\Theta }(m\cdot n)$: השינויים בLCS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LCS(i, j) מורידה (לפחות) את אחד הארגומנטים שלה ב1, ולכן היא יכולה להיקרא לכל היותר $m+n$ פעמים. הסיבוכיות, לכן, היא $\mathrm{\Theta }(m\cdot n)$ + $O(m+n)$ = $\mathrm{\Theta }(m\cdot n)$.