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

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

עריכה

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

  1. כפי שצוין בשאלה, נגדיר את אורך   כ , ואת אורך   כ .
  2. נסמן את הרישה ה  של מחרוזת   כ . במילים אחרות,  .‏
  3. נגדיר כ  את אורך הLCS של   ו . במילים אחרות,   היא אורך תת-הסדרה הארוכה ביותר המשותפת ל  ו .


 

עכשיו תורכם:

וודא שהמך מבין מדוע לפי הגדרה זו,   הוא אורך הLCS של   ו .



משפט:

  מקיים את הנוסחה הבאה:

  1. אם   או  ,‏ אז  .
  2. אם לא,‏ אז:
    1. אם  , אז  .
    2. אם  , אז  .



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


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

נניח ש . ראשית, קל לראות שבהכרח תווה האחרון של   הוא   - אם זה לא היה המצב, אז   גם היא מחרוזת משותפת ל  ו , דבר שנוגד עפ"י ההגדרה את היותה של   תת-המחרוזת המשותפת הארוכה ביותר. נחשוב כעת על כל תתי המחרוזות המשותפות מהצורה  : עבור כל אחת מהן, קל לראות ש  היא תת-מחרוזת משותפת ל  ו , ולכן בהכרח הארוכה שבהן היא זו שהרישה שלה היא הLCS של   ו .

לחלופין, נניח ש ; יש שלוש אפשרויות:

  1.  מסתיימת ב  - אם כן, הLCS בהכרח מהצורה  , כאשר   היא הLCS של   ו .
  2.   מסתיימת ב  - אם כן, הLCS בהכרח מהצורה  , כאשר   היא הLCS של   ו .
  3.  אינה מסתיימת ב , וכן אינה מסתיימת ב  - אם זה המצב, אז הLCS של   ו  הוא הLCS של   ו  (וכן גם הLCS של   ו ), כך ששתי הבדיקות הקודמות מכסות כבר (פעמיים אפילו) מקרה זה.


 

מציאת אורך ה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, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה בעבר.

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

עריכה

נגדיר את   כזמן שאורכת LCS-Length בהנחה שכל אחת מקריאותיה הרקורסיביות היא  . קל לראות ש .

זמן הריצה של LCS-Length(m, n) חסום מלמעלה על ידי  . חוץ מכך ישנו האתחול 1-4 שאורך גם כן  . הזמן הכולל, לכן, הוא  .

הדפסת איברי ה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 מתארת בכניסה ה  את ההחלטה לגבי הLCS של   ו :

  1. 'x' מסמלת את ההחלטה לוותר על התו האחרון ב .
  2. 'y' מסמלת את ההחלטה לוותר על התו האחרון ב .
  3. 'b' מסמלת את ההחלטה לוותר על התו האחרון בשניהם. זה בדיוק המצב בו   נמצא כחלק מה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])

קל לראות שהסיבוכיות עדיין  : השינויים בLCS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LCS(i, j) מורידה (לפחות) את אחד הארגומנטים שלה ב1, ולכן היא יכולה להיקרא לכל היותר   פעמים. הסיבוכיות, לכן, היא   +   =  .