Longest Common Substring

Q: ما هو التعقيد الزمني لأطول سلسلة فرعية مشتركة؟

يستغرق حل البرمجة الديناميكية زمنًا قدره O(n × m) ، ويستهلك ذاكرة قدرها O(m) باستخدام صف واحد. أما التوسّع انطلاقًا من كل زوج من نقاط البداية فيستغرق O(n × m × min(n, m)) في أسوأ الحالات. وتصل آلة الحالات المنتهية اللاحقة إلى نحو O(n + m) ، على حساب برنامج أطول بكثير.

Q: كيف تُعيد أطول سلسلة فرعية مشتركة نفسها؟

كلما تجاوزت خلية القيمة best ، سجّل أيضًا الموضع i في s1 الذي تنتهي عنده تلك الكتلة. في النهاية، يكون الجزء الفرعي هو أحرف s1 وعددها best التي تنتهي عند ذلك الموضع. تضمن مقارنة أكبر من الصارمة الاحتفاظ بأول كتلة أطول يتم العثور عليها في s1 .

متوسطالبرمجة الديناميكية

+10

لديك سلسلتان، s1 وs2. السلسلة الفرعية هي تسلسل متصل من الأحرف مأخوذ من سلسلة، مثل ork من clockwork. أوجد أطول سلسلة فرعية مشتركة بين s1 وs2، وأعِد طولها. إذا لم يوجد أي حرف مشترك بين السلسلتين، فالإجابة هي 0.

الدالة

longestCommonSubstring(s1: string, s2: string) → integer

s1string: السلسلة النصية الأولى
s2string: السلسلة النصية الثانية
تُرجعinteger: طول أطول تسلسل من الأحرف يوجد في كلتا السلسلتين

القيود

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 وs2 يتكونان من أحرف إنجليزية صغيرة.

أمثلة

المدخلات: s1 = "clockwork"s2 = "workshop"
المخرجات: 4
الشرح: تُغلق work السلسلة clockwork وتفتح workshop، لذا فهي سلسلة فرعية مشتركة بطول 4، ولا تظهر أي كتلة أطول في كلتيهما.

المدخلات: s1 = "hammer"s2 = "harmed"
المخرجات: 2
الشرح: تظهر ha وme في كلتا الكلمتين، لكن لا توجد سلسلة من ثلاثة أحرف. تحتوي كلتا الكلمتين على h وa وm وe بهذا الترتيب، لكن توجد r بين a وm في harmed.

سؤال إضافي

هل يمكنك اختبار ما إذا كانت توجد سلسلة فرعية مشتركة بطول محدد L في زمن يقارب O(n + m) باستخدام تجزئة متدحرجة، ثم إجراء بحث ثنائي على L؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

إن تمديد المطابقة انطلاقًا من كل زوج من مواضع البداية يعيد قراءة الأحرف نفسها. انظر إلى الموضع الذي ينتهي عنده المقطع بدلًا من ذلك: فالمقطع المشترك الذي ينتهي عند s1[i] وs2[j] أطول بحرف واحد من المقطع الذي ينتهي عند الحرفين السابقين لهما، أو يكون فارغًا إذا اختلف الحرفان. يجيب جدول بهذه الأطوال في زمن O(n × m).

الامتداد انطلاقًا من كل زوج من مواضع البداية

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

تبدأ كل سلسلة فرعية مشتركة عند موضع ما i في s1 وعند موضع ما j في s2. لكل زوج، تقدّم خطوةً خطوة ما دامت الأحرف متطابقة، وعدّ الخطوات؛ وأكبر عدد هو الإجابة.

يجعل النص المتكرر عمليات التقدّم طويلة. عندما تكون كلتا السلسلتين مؤلفتين من 1000 نسخة من a، يتقدّم كل زوج حتى نهاية اللاحقة الأقصر: نحو 3.3 × 10^8 مقارنةً بين الأحرف. تتكرر عملية التقدّم من (i, j) بكاملها في عملية التقدّم من (i+1, j+1)، مع تأخير حرف واحد.

الخوارزمية

عيّن best = 0.
لكل i في s1 ولكل j في s2، عيّن k = 0.
ما دام كلٌّ من i+k وj+k ضمن سلسلتيهما وs1[i+k] == s2[j+k]، أضف 1 إلى k.
احتفظ بأكبر قيمة لـ k في best، ثم أعدها.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

جدول أطوال الكتل التي تنتهي عند كل زوج

الفكرة

لتكن run[i][j] طول أطول مقطع مشترك ينتهي تحديدًا عند s1[i-1] وs2[j-1]؛ ويحتوي الصف 0 والعمود 0 على القيمة 0. يجب أن يحتوي هذا المقطع على الحرفين كليهما. إذا اختلفا، فلا يوجد مقطع وتكون الخلية 0. وإذا تطابقا، فالمقطع هو هذا الزوج مضافًا إليه المقطع الذي ينتهي قبل حرف واحد في كلتا السلسلتين: run[i-1][j-1] + 1. تنتهي كل سلسلة فرعية مشتركة في موضع ما، لذا فالإجابة هي أكبر خلية، أينما كان موقعها.

في hammer وharmed، يعطي الحرفان h القيمة 1، ثم يمدّ الحرفان a المقطع إلى 2، وبعدها يكسر الحرف r المقطع. يأتي الحرف m الثاني في hammer بعد عدم تطابق بين m وr، ويقابله الحرف m في harmed، لذا يبدأ بقيمة 1، ثم يرفع الحرفان e القيمة إلى 2. لا تصل أي خلية إلى 3.

مقارنة واحدة لكل خلية: نحو مليون مقارنة لسلسلتين من 1000 حرف، مهما كان النص.

الخوارزمية

خصّص لـ run صفوفًا بعدد n+1 وأعمدة بعدد m+1، واجعل قيمها جميعًا 0، ثم عيّن best = 0.
كرّر i من 1 إلى n، وداخل ذلك كرّر j من 1 إلى m، مع مقارنة s1[i-1] بـ s2[j-1].
عند التطابق، عيّن run[i][j] = run[i-1][j-1] + 1 وحدّث best.
عند عدم التطابق، اترك قيمة الخلية 0.
أعِد best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

صف واحد، يُحدَّث من اليمين إلى اليسار

الفكرة

تقرأ كل خلية الخلية التي تقع قطريًا إلى أعلى وإلى اليسار فقط. لذا يمكن لمصفوفة واحدة run تضم m+1 من الأعداد أن تحتوي الجدول إذا مررت على j من اليمين إلى اليسار: عندما تكتب run[j]، تظل الخانة run[j-1] محتفظة بالقيمة الخاصة بالحرف السابق من s1، وهي الخلية القطرية.

يجب الآن أن يؤدي عدم التطابق إلى كتابة 0 صراحةً، لأن الخانة لا تزال تحتفظ بعدد من الصف السابق. يظل الزمن O(n × m)، وتنخفض الذاكرة من نحو 10^6 عددًا إلى 1001.

الخوارزمية

أنشئ مصفوفة run مكوّنة من m+1 أصفار، واجعل best = 0.
لكل حرف ch من s1، مرّ على j من m نزولًا إلى 1.
إذا كان ch == s2[j-1]، فاجعل run[j] = run[j-1] + 1 وحدّث best.
وإلا، فاجعل run[j] = 0.
أعِد best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

أخطاء شائعة وحالات حدّية

إرجاع الخانة الأخيرة. لا تغطي run[n][m] إلا الكتل التي تنتهي عند الحرفين الأخيرين معًا. بالنسبة إلى abc وabd تكون النتيجة 0، بينما يعطي ab النتيجة 2.
نسخ الجار الأكبر عند عدم التطابق. هذه هي قاعدة التتابع الجزئي، وتسمح للكتلة بتجاوز الحروف: مع hammer وharmed تعطي النتيجة 4 بدلًا من 2.
المرور على الصف الواحد من اليسار إلى اليمين. تُستبدل قيمة القطر قبل قراءتها، لذا تعطي a مقارنةً بـ aa النتيجة 2.
تجاوز إعادة الضبط في الصف الواحد. يبقى طول من الحرف السابق في s1، ثم يمتد لاحقًا إلى كتلة غير موجودة.
المرور على القوة الغاشمة من دون التحقق من الحدود. عند مقارنة zzzz بـ zz، يقرأ البرنامج بعد نهاية السلسلة الأقصر.

أسئلة شائعة3

ما الفرق بين أطول سلسلة فرعية مشتركة وأطول تسلسل مشترك؟

السلسلة الفرعية هي تتابع متصل من الحروف؛ أما التتابع الجزئي فيحافظ على الترتيب لكنه قد يتخطى بعض الحروف. بالنسبة إلى hammer وharmed، يبلغ طول أطول سلسلة فرعية مشتركة 2، ويبلغ طول أطول تتابع جزئي مشترك 4 (hame). في الجداول، يؤدي عدم التطابق إلى إعادة ضبط خلية السلسلة الفرعية إلى 0، بينما يجعل خلية التتابع الجزئي تنسخ القيمة الأكبر من جارتيها.

ما هو التعقيد الزمني لأطول سلسلة فرعية مشتركة؟

يستغرق حل البرمجة الديناميكية زمنًا قدره O(n × m)، ويستهلك ذاكرة قدرها O(m) باستخدام صف واحد. أما التوسّع انطلاقًا من كل زوج من نقاط البداية فيستغرق O(n × m × min(n, m)) في أسوأ الحالات. وتصل آلة الحالات المنتهية اللاحقة إلى نحو O(n + m)، على حساب برنامج أطول بكثير.

كيف تُعيد أطول سلسلة فرعية مشتركة نفسها؟

كلما تجاوزت خلية القيمة best، سجّل أيضًا الموضع i في s1 الذي تنتهي عنده تلك الكتلة. في النهاية، يكون الجزء الفرعي هو أحرف s1 وعددها best التي تنتهي عند ذلك الموضع. تضمن مقارنة أكبر من الصارمة الاحتفاظ بأول كتلة أطول يتم العثور عليها في s1.

def longestCommonSubstring(s1, s2):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

s1 = "clockwork"
s2 = "workshop"

الإخراج المتوقع

Longest Common Substring

الدالة

القيود

أمثلة

تلميحات

الحل

الامتداد انطلاقًا من كل زوج من مواضع البداية

جدول أطوال الكتل التي تنتهي عند كل زوج

صف واحد، يُحدَّث من اليمين إلى اليسار

أخطاء شائعة وحالات حدّية

أسئلة شائعة3

مسائل مشابهة