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. يأتي الحرفان s وt في النهاية فيlongestلكنهما يأتيان في البداية فيstone، لذا فإن استخدامهما يعطيstكحد أقصى.
- المدخلات
- text1 = "pear"text2 = "reap"
- المخرجات
- 2
- الشرح
- تظهر
eaفي كلتا الكلمتين. يقع الحرفان p وr على جانبين متقابلين منeaفي الكلمتين، لذا لا يمكن لأيٍّ منهما الانضمام إليها، والإجابة هي 2.
- المدخلات
- text1 = "cat"text2 = "dog"
- المخرجات
- 0
- الشرح
- لا تشترك الكلمتان في أي حرف، لذا فإن التسلسل الجزئي المشترك الوحيد هو التسلسل الفارغ، وطوله 0.
سؤال إضافي
هل يمكنك إرجاع أطول تسلسل فرعي مشترك نفسه، إلى جانب طوله؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر إلى الحرف الأخير من كل سلسلة نصية. ماذا يمكنك أن تقول عن الإجابة عندما يكون الحرفان متساويين، وماذا عندما يختلفان؟
إذا تطابقت الحروف، فزاوج بينها، وتبقى المشكلة نفسها في كلتا السلسلتين بعد إزالة ذلك الحرف. وإذا اختلفت، فهذا يعني أن واحدًا منهما على الأقل لن يُستخدم، لذا جرّب إزالة كلٍّ منهما واختر الإجابة الأفضل.
تتكرر أزواج البادئات نفسها مرارًا وتكرارًا. خزّن الإجابة لكل زوج من أطوال البادئات
(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 استدعاء، مع أن هناك فقط (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 بادئة فارغة، ويكون الصف 0 والعمود 0 مساويين لـ 0. قارن الحرفين الأخيرين من البادئتين، text1[i-1] وtext2[j-1]: إذا كان الحرفان متساويين، فهما يشكّلان زوجًا، dp[i-1][j-1] + 1؛ وإذا كانا مختلفين، فأسقط أحدهما، max(dp[i-1][j], dp[i][j-1]). هذا هو الاستدعاء الذاتي عند قراءته من النهاية.
تقرأ كل خلية الخلايا التي فوقها، وإلى يسارها، وفوقها وإلى يسارها قطريًا، لذا فإن ملء الصفوف من اليسار إلى اليمين يضمن دائمًا أن تكون تلك الخلايا جاهزة. بالنسبة إلى pear وreap، يكون صف pea هو [0, 0, 1, 2, 2]؛ وقيمة خليته عند rea هي 2 لأن a يطابق a، فتُضاف واحدًا إلى قيمة الخلية عند pe وre.
يستغرق التعامل مع سلسلتين من 1000 حرف نحو 10^6 خطوة ذات زمن ثابت.
الخوارزمية
- أنشئ جدولًا
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]احتفِظ بصفَّين فقط
الفكرة
بمجرد اكتمال صف، لن تُقرأ الصفوف التي تعلوه مرة أخرى. احتفظ بـ prev للصف المكتمل وبـ cur للصف الجاري ملؤه، وبدّل بينهما بعد كل صف. تظل علاقة التكرار والترتيب كما هما.
لا تعتمد الإجابة على أي السلسلتين تأتي أولًا، لذا اجعل الصفوف تمتد على طول السلسلة الأقصر. عندئذٍ يحتوي كل صف على min(n, m) + 1 عددًا: 1001 بدلًا من مليون خلية لأكبر المدخلات، مع عدد الخطوات نفسه، وهو 10^6.
الخوارزمية
- إذا كان
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. - الكتابة في الصف الذي ما زلت تقرأ منه. عند استخدام صفين، يجب أن تأتي كل قيمة من الصف العلوي من
prev، ويجب أن تظلcur[0]مساوية لـ 0. - تخزين نتائج الاستدعاءات العودية مؤقتًا في Python لسلاسل نصية مكوّنة من 1000 حرف. يصل عمق الاستدعاءات إلى 2000، متجاوزًا الحد الافتراضي البالغ 1000.
أسئلة شائعة3
ما هو التعقيد الزمني لأطول تسلسل مشترك؟
يعمل حل الجدول في زمن O(n × m)، خلية واحدة لكل زوج من البادئات. ويحتاج إلى ذاكرة O(n × m) للجدول الكامل، أو O(min(n, m)) باستخدام صفين. أما الاستدعاء الذاتي البسيط من دون جدول فزمنه أُسّي.
ما الفرق بين أطول تسلسل مشترك وأطول سلسلة فرعية مشتركة؟
يمكن للمتتالية الجزئية تخطي الأحرف ما دام الترتيب محفوظًا؛ أما السلسلة الفرعية فهي مجموعة من الأحرف المتجاورة. بالنسبة إلى stone وlongest، فإن أطول متتالية جزئية مشتركة هي one (3)، لكن أطول سلسلة فرعية مشتركة هي on (2). يعيد جدول السلاسل الفرعية ضبط الخلية إلى 0 عند عدم التطابق بدلًا من نسخ قيمة خلية مجاورة.
ما علاقة LCS بأدوات diff ومسافة التحرير؟
يعرض الفرق بين نسختين من ملف أطول تسلسل مشترك من أسطرهما، ويُظهر كل سطر آخر على أنه مُضاف أو محذوف. أقل عدد من عمليات الإدراج والحذف اللازمة لتحويل سلسلة نصية إلى الأخرى هو n + m - 2 × LCS. تسمح مسافة التحرير أيضًا باستبدال حرف، لذا فهي تحتاج إلى جدول خاص بها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def longestCommonSubsequence(text1, text2):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
text1 = "stone" text2 = "longest"
الإخراج المتوقع
3