Longest Common Subsequence
لديك سلسلتان، text1 وtext2. يحافظ التسلسل الفرعي من سلسلة على بعض أحرفها بترتيبها الأصلي ويحذف الباقي؛ ولا يشترط أن تكون الأحرف المحتفَظ بها متجاورة. أعد طول أطول سلسلة تكون تسلسلًا فرعيًا في كلتا السلسلتين، أو 0 إذا لم يكن بين السلسلتين أي حرف مشترك.
الدالة
- text1string
- السلسلة النصية الأولى
- text2string
- السلسلة النصية الثانية
- تُرجعinteger
- طول أطول تتابع مشترك
القيود
1 ≤ text1.length ≤ 10001 ≤ text2.length ≤ 1000- تحتوي كلتا السلسلتين النصيتين على أحرف إنجليزية صغيرة فقط.
أمثلة
- المدخلات
- text1 = "stone"text2 = "longest"
- المخرجات
- 3
- الشرح
- تظهر الأحرف o وn وe بهذا الترتيب في كلتا الكلمتين، لذا فإن
oneهي سلسلة فرعية مشتركة طولها 3. فيlongestيأتي الحرفان s وt أخيرًا، بينما يأتيان أولًا فيstone، لذا فإن السلسلة الفرعية المشتركة التي تستخدمهما لا يمكن أن تكون إلاst، وهي أقصر.
- المدخلات
- text1 = "pear"text2 = "reap"
- المخرجات
- 2
- الشرح
- تظهر
eaفي كلتا الكلمتين. يقع الحرفان p وr على جانبين متقابلين منeaفي الكلمتين، لذا لا يمكن لأيٍّ منهما الانضمام إليها، والإجابة هي 2.
- المدخلات
- text1 = "cat"text2 = "dog"
- المخرجات
- 0
- الشرح
- لا تشترك الكلمتان في أي حرف، لذا فإن المتتالية الجزئية المشتركة الوحيدة هي المتتالية الفارغة، وطولها 0.
+19 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إرجاع أطول تسلسل فرعي مشترك نفسه، وليس طوله فقط؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الحرف الأخير من كل سلسلة. ماذا يمكنك أن تقول عن الإجابة عندما يكون الحرفان متساويين، وماذا عندما يختلفان؟
إذا تطابقت الحروف، فقم بإقرانها، وتكون المسألة المتبقية هي نفسها لكلا السلسلتين بعد إزالة ذلك الحرف. وإذا اختلفت، فهذا يعني أن واحدًا على الأقل منهما لن يُستخدم، لذا جرّب إزالة كلٍّ منهما واحتفظ بالإجابة الأفضل.
تتكرر أزواج البوادئ نفسها مرارًا وتكرارًا. خزّن الإجابة لكل زوج من أطوال البوادئ
(i, j)في جدول، وابدأ بالبوادئ الفارغة، التي تكون إجابتها 0، واملأ الجدول صفًا بعد صف، ثم اقرأ الإجابة من الخلية الأخيرة.
الحل
إن مطابقة الأحرف بطريقة جشعة لا تنجح. فقد يطابق الحرف مواضع كثيرة في السلسلة الأخرى، وقد تمنع المطابقة الأولى مطابقةً أفضل: فمطابقة حرف c في cab مع حرف c في نهاية abc لا تترك شيئًا للحرفين a وb، بينما يؤدي تخطيه إلى العثور على ab. والفكرة التي تحل هذه المشكلة هي أن الإجابة لبادئتين تعتمد فقط على إجابات بادئتين أقصر قليلًا. يحل جدول من الأعداد حجمه (n+1) × (m+1) كل زوج مرة واحدة، وبما أن كل صف يقرأ الصف الذي فوقه فقط، فيكفي صفّان.
قارن الأحرف الأولى باستخدام الاستدعاء الذاتي
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لتكن lcs(i, j) الإجابة عن اللاحقتين text1[i:] وtext2[j:]. انظر إلى الحرفين الأولين فيهما. إذا كانا متساويين، فاقرن بينهما: إذ يمكن لمتتالية جزئية مشتركة أطول لا تستخدم هذا الزوج أن تستبدل زوجها الأول بهذا الزوج من دون أن تقصر. لذا فالإجابة هي 1 + lcs(i+1, j+1).
إذا اختلف الحرفان، فلا يمكن استخدامهما معًا، لأن كلًّا منهما لا يمكن أن يُطابق إلا حرفًا لاحقًا في السلسلة الأخرى، وعندها ستتقاطع الأزواج. لذا يمكن إسقاط أحدهما: الإجابة هي max(lcs(i+1, j), lcs(i, j+1)). عندما تكون إحدى اللاحقتين فارغة، لا يوجد أي شيء مشترك، وتكون الإجابة 0.
هذه الطريقة بطيئة لأن كل حالة عدم تطابق تبدأ استدعاءين. إذا لم تشترك السلسلتان في أي حرف، فسيحدث عدم تطابق في كل استدعاء إلى أن تنفد إحدى السلسلتين، ويزداد عدد الاستدعاءات مثل عدد طرق تشابك السلسلتين. بالنسبة إلى سلسلتين طول كل منهما 20 حرفًا، يبلغ ذلك نحو 2.8 × 10^11 استدعاء؛ أما الاختبارات الكبيرة فتحتوي على 1000 حرف في كل سلسلة. ومع ذلك، لا يوجد سوى (n+1) × (m+1) زوجًا مختلفًا (i, j)، لذا فإن كل استدعاء تقريبًا يكرر استدعاءً سابقًا.
الخوارزمية
- اكتب
lcs(i, j)لللاحقتين اللتين تبدآن عندiوj. - إذا تجاوز
iأوjنهاية سلسلته، فأعد 0. - إذا كان
text1[i] == text2[j]، فأعد1 + lcs(i+1, j+1). - وإلا فأعد
max(lcs(i+1, j), lcs(i, j+1)). - الإجابة هي
lcs(0, 0).
def longestCommonSubsequence(text1, text2):
def lcs(i, j):
# The longest common subsequence of text1[i:] and text2[j:]
if i == len(text1) or j == len(text2):
return 0
if text1[i] == text2[j]:
return 1 + lcs(i + 1, j + 1)
return max(lcs(i + 1, j), lcs(i, j + 1))
return lcs(0, 0)املأ جدول البوادئ
الفكرة
الحالة. ليكن dp[i][j] أطول تتابع مشترك بين الأحرف i الأولى من text1 والأحرف j الأولى من text2. يتيح لنا العمل مع البادئات أن يعني الفهرس 0 سلسلة فارغة.
العلاقة التكرارية. قارن الحرفين الأخيرين من البادئتين، text1[i-1] وtext2[j-1]. إذا كانا متساويين، فاجمع بينهما: dp[i][j] = dp[i-1][j-1] + 1. وإذا لم يكونا متساويين، فاحذف أحدهما: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). هذا هو المنطق نفسه المتبع في الاستدعاء التكراري، لكن بقراءته من النهاية. الحالة الأساسية: قيمة الصف 0 والعمود 0 هي 0، لأن البادئة الفارغة لا تشترك في أي شيء مع أي سلسلة. الترتيب: تعتمد كل خلية على الخلية التي فوقها، والخلية التي على يسارها، والخلية القطرية التي تقع أعلى اليسار، لذا فإن ملء الجدول صفًا بعد صف، من اليسار إلى اليمين، يضمن أن تكون قيمها جاهزة دائمًا. الإجابة هي dp[n][m].
بالنسبة إلى pear وreap، يكون الصف الخاص بـ pea هو [0, 0, 1, 2, 2]. قيمة الخلية الخاصة بـ rea هي 2 لأن الحرف a يطابق الحرف a، لذا فهي تساوي قيمة الخلية الخاصة بـ pe وre، وهي 1، زائد واحد. تقارن الخلية الأخيرة، الخاصة بـ pear مقابل reap، بين r وp، وهما مختلفان، لذا تأخذ القيمة الأكبر من الخليتين المجاورتين، وهي 2.
يحتوي الجدول على (n+1) × (m+1) خلية، ويتطلب حساب كل خلية وقتًا ثابتًا: نحو 10^6 خطوة لسلسلتين طول كل منهما 1000 حرف. تملأ نسخة تستخدم التخزين المؤقت للاستدعاء التكراري الخلايا نفسها، لكنها تُجري استدعاءات متداخلة يصل عمقها إلى n + m، ما يؤدي إلى تجاوز سعة مكدس الاستدعاءات الافتراضي في لغات مثل Python.
الخوارزمية
- أنشئ جدولًا
dpمكوّنًا من أصفار بأبعاد(n+1) × (m+1). - لكل
iمن 1 إلىnولكلjمن 1 إلىm، قارنtext1[i-1]بـtext2[j-1]. - عند التطابق، عيّن
dp[i][j] = dp[i-1][j-1] + 1. - وإلا، عيّن
dp[i][j] = max(dp[i-1][j], dp[i][j-1]). - أعِد
dp[n][m].
def longestCommonSubsequence(text1, text2):
n, m = len(text1), len(text2)
# dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
# Row 0 and column 0 stay 0: an empty prefix has nothing in common.
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]احتفِظ بصفَّين فقط
الفكرة
لا يقرأ الصف i من الجدول إلا الصف i-1 وخلاياه السابقة في الصف نفسه. بعد اكتمال صف، لا يُقرأ أي صف فوقه مرة أخرى. لذا احتفِظ بمصفوفتين، prev للصف المكتمل وcur للصف الجاري ملؤه، وبدّل بينهما بعد كل صف. تظل علاقة العودية والترتيب كما هما تمامًا.
لا تهتم المتتالية الجزئية المشتركة بين سلسلتين أيتهما تأتي أولًا، لذا يمكنك تبديلهما وجعل الصفوف تسير على طول السلسلة الأقصر. عندها يحتوي كل صف على min(n, m) + 1 عددًا: 1001 بدلًا من مليون خلية للمدخلات الأكبر، مع العدد نفسه من خطوات العمل، وهو 10^6.
يمثل العنصر الأول في كل صف بادئة فارغة من السلسلة الأقصر، لذا يجب أن يبقى 0. الإجابة هي العنصر الأخير في آخر صف مكتمل.
الخوارزمية
- إذا كان
text2أطول منtext1، فبدّلهما. - أنشئ
prevوcur، يحتوي كلٌّ منهما علىm + 1أصفار، حيث إنmهو الطول الأقصر. - لكل حرف في
text1، املأcur[1..m]باستخدام القاعدة نفسها المتبعة في الجدول، مع قراءةprevللصف السابق. - بدّل
prevوcur. - أعِد
prev[m].
def longestCommonSubsequence(text1, text2):
if len(text2) > len(text1):
text1, text2 = text2, text1 # keep the rows as short as the shorter string
m = len(text2)
# prev[j]: the answer for the previous prefix of text1 and text2[:j]
prev = [0] * (m + 1)
for ch in text1:
cur = [0] * (m + 1)
for j in range(1, m + 1):
if ch == text2[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = max(prev[j], cur[j - 1])
prev = cur
return prev[m]
أخطاء شائعة وحالات حدّية
علاقة التكرار قصيرة، ومعظم الأخطاء تكون بسبب فرق بمقدار واحد أو إضافة تطابق في المكان الخطأ.
- الخلط بين فهارس الجدول وفهارس السلسلة النصية. تقارن الخلية
dp[i][j]بينtext1[i-1]وtext2[j-1]، لأن الصف 0 يمثل البادئة الفارغة. - عند التطابق، إضافة واحد إلى
max(dp[i-1][j], dp[i][j-1])بدلًا من إضافته إلىdp[i-1][j-1]. قد يؤدي ذلك إلى استخدام الحرف نفسه مرتين: فمقارنةaaمعaستُرجع 2 بدلًا من 1. - البحث عن التطابق بطريقة جشعة باستخدام مؤشرين. تؤدي مقارنة
cabمعabcإلى مطابقة حرفَي c وإرجاع 1، بينما تعطيabالنتيجة 2. - الكتابة في الصف الذي ما زلت تقرأ منه. عند استخدام صفين، يجب أن تأتي كل قيمة من الصف السابق من
prev، ويجب أن تبقىcur[0]مساويةً لـ 0. - حل مسألة أطول سلسلة فرعية مشتركة عن طريق الخطأ. يمكن للتتابع تخطي الأحرف؛ أما السلسلة الفرعية فلا يمكنها ذلك.
- استخدام التخزين المؤقت مع الاستدعاء الذاتي على سلاسل نصية طولها 1000 حرف. يصل عمق الاستدعاءات إلى 2000، متجاوزًا الحد الافتراضي في Python البالغ 1000.
أسئلة شائعة4
ما هو التعقيد الزمني لأطول تتابع مشترك؟
يعمل حل الجدول في زمن O(n × m)، حيث n وm هما الطولان: فهو يملأ خلية واحدة لكل زوج من البادئات. يحتاج إلى ذاكرة O(n × m) للجدول الكامل، أو O(min(n, m)) باستخدام صفّين. أما الاستدعاء الذاتي البسيط دون جدول فزمنه أُسّي.
ما الفرق بين أطول تتابع مشترك وأطول سلسلة فرعية مشتركة؟
يمكن للتتابع الجزئي تخطي الأحرف ما دام ترتيبها محفوظًا، بينما السلسلة الفرعية هي مجموعة من الأحرف المتجاورة. بالنسبة إلى stone وlongest، فإن أطول تتابع جزئي مشترك هو one (3)، لكن أطول سلسلة فرعية مشتركة هي on (2). يستخدم إصدار السلسلة الفرعية جدولًا مشابهًا، لكن عدم التطابق يعيد الخلية إلى 0 بدلًا من نسخ قيمة خلية مجاورة.
كيف تطبع أطول تتابع مشترك بحد ذاته؟
املأ الجدول كاملًا، ثم ارجع من dp[n][m]. عندما يتطابق الحرفان في الخلية الحالية، يكون ذلك الحرف جزءًا من الإجابة: سجّله وانتقل قطريًا إلى أعلى وإلى اليسار. وإلا فانتقل إلى الجار الأعلى أو الأيسر الذي يحمل القيمة الأكبر. اعكس ترتيب الحروف المسجّلة في النهاية. لا يمكن لنسخة الصفّين أن تفعل ذلك، لأنها تخلّصت من الصفوف السابقة.
ما علاقة LCS بأدوات diff ومسافة التحرير؟
يُحدِّد الفرق بين إصدارين من ملف أطول تتابع مشترك لأسطرهما؛ ويُعرض كل سطر خارج هذا التتابع على أنه مُضاف أو محذوف. وبالمثل، فإن أقل عدد من عمليات الإدراج والحذف اللازمة لتحويل سلسلة إلى الأخرى هو n + m - 2 × LCS. تسمح مسافة التحرير أيضًا باستبدال حرف، لذا تستخدم جدولًا خاصًا بها يتضمن خيارًا ثالثًا لكل خلية.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def longestCommonSubsequence(text1, text2):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
text1 = "stone" text2 = "longest"
المتوقع
3