Find the First Occurrence in a String

Q: ما التعقيد الزمني لإيجاد أول ظهور لسلسلة نصية؟

يستغرق فحص كل موضع بداية زمنًا قدره O(n · m) في أسوأ الحالات، حيث يمثّل n و m طولي السلسلة haystack والإبرة، ويستخدم مساحة إضافية قدرها O(1) . تستغرق خوارزمية Knuth-Morris-Pratt زمنًا قدره O(n + m) ومساحة قدرها O(m) لجدولها، مهما كانت الأحرف.

سهلالمصفوفات والسلاسل النصية مؤشران

+10

تحصل على سلسلتين نصيتين، haystack وneedle. أعد الفهرس في haystack الذي يبدأ عنده أول ظهور لـneedle، مع بدء العد من 0. إذا لم تظهر needle مطلقًا في haystack، فأعد -1. اكتب خوارزمية البحث بنفسك بدلًا من استدعاء دالة مضمّنة للبحث عن سلسلة فرعية، مثل find أو indexOf.

الدالة

strStr(haystack: string, needle: string) → integer

haystackstring: النص المراد البحث فيه
needlestring: السلسلة النصية التي تبحث عنها
تُرجعinteger: الفهرس الذي يبدأ عنده أول ظهور لـ needle، أو ‎-1‎ إذا لم يوجد

القيود

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
تحتوي كلتا السلسلتين على أحرف إنجليزية صغيرة فقط.
needle قد تكون أطول من haystack. عندئذٍ لا يمكن أن تظهر، وتكون الإجابة -1.

أمثلة

المدخلات: haystack = "bananarama"needle = "ana"
المخرجات: 1
الشرح: الأحرف عند الفهارس 1 و2 و3 تُكوّن ana. تبدأ نسخة ثانية عند الفهرس 3 وتتداخل مع النسخة الأولى، لكن الإجابة هي النسخة الأولى، لذا فهي 1.

المدخلات: haystack = "pineapple"needle = "apples"
المخرجات: -1
الشرح: تبدأ apple عند الفهرس 4، وينتهي النص بعده مباشرةً، لذا لا يوجد حرف لمطابقة الحرف s الأخير من السلسلة المراد البحث عنها. لا توجد نسخة كاملة من apples، لذا تكون الإجابة -1.

المدخلات: haystack = "abcabcabd"needle = "abcabd"
المخرجات: 3
الشرح: تطابق المحاولة عند الفهرس 0 خمسة أحرف، abcab، ثم تصادف c بينما تتوقع الإبرة d. تبدأ النسخة التي تنجح عند الفهرس 3 وتنتهي بالحرف d الأخير.

سؤال إضافي

هل يمكنك إرجاع كل فهرس تبدأ عنده needle، بما في ذلك النسخ المتداخلة، مع الحفاظ على زمن تنفيذ O(n + m)؟

تلميحات

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

فُتح 0 من 3

الحل

مقارنة needle عند كل موضع بداية صحيحة، لكنها بطيئة عندما تكاد المطابقات تنجح: إذ يُهمل التطابق الجزئي الطويل الذي يفشل قرب نهايته، ثم تقرأ نقطة البداية التالية معظم الأحرف نفسها مجددًا. تحتفظ خوارزمية Knuth-Morris-Pratt بهذا العمل. يوضّح جدول مُنشأ من needle وحدها مقدار ما يمكن الاستفادة منه من تطابق جزئي فاشل، لذا لا يتراجع الفحص في haystack مطلقًا، وينتهي في O(n + m).

تحقّق من كل موضع بداية

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

الفكرة

لنسمِّ طولي haystack وneedle بـn وm على التوالي. يمكن أن تبدأ نسخة من نمط البحث عند أي فهرس من 0 إلى n-m. جرّب نقاط البداية هذه من اليسار إلى اليمين. عند كل نقطة، قارِن نمط البحث بالنص حرفًا حرفًا، وتوقّف عند أول اختلاف. أول نقطة بداية تتطابق فيها الأحرف الـm كلها هي الإجابة، والبحث من اليسار إلى اليمين يجعلها أول نسخة.

آخر نقطة بداية هي n-m، لأن النسخة التي تبدأ بعد ذلك ستتجاوز نهاية النص haystack. وينطبق الحد نفسه عندما يكون نمط البحث أطول من النص: لا توجد نقطة بداية لتجربتها، وتصل الحلقة إلى -1.

تظهر الكلفة عندما تتطابق معظم الأحرف. خذ نصًا haystack مكوّنًا من 50,000 حرف a، ونمط بحث مكوّنًا من 24,999 حرف a يتبعه حرف b. تقارن كل واحدة من نقاط البداية الـ25,001 عدد 25,000 حرف قبل أن تصل إلى b، أي أكثر من 6 × 10^8 مقارنة للحصول على إجابة -1.

الخوارزمية

لتكن n وm طولي haystack وneedle.
لكل start من 0 إلى n-m، اضبط j على 0.
ما دام j < m وhaystack[start + j] يساوي needle[j]، فزِد j.
إذا بلغ j القيمة m، فهذا يعني أن جميع الأحرف تطابقت: أعد start.
إذا لم ينجح أي موضع بداية، فأعد -1.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Knuth-Morris-Pratt

الفكرة

انظر إلى ما تتخلّص منه القوة الغاشمة. عند البحث عن abcabd في abcabcabd، تطابق المحاولة عند الفهرس 0 السلسلة abcab ثم تفشل. تنتهي هذه الأحرف الخمسة بـ ab، وهي أيضًا بداية سلسلة البحث. لذا، بعد عدم التطابق، يكون حرفان من المحاولة المفيدة التالية قد تطابقا بالفعل، ويمكنك المتابعة من الموضع نفسه في النص.

الحافة في سلسلة نصية هي بادئة أقصر تكون أيضًا لاحقة، مثل ab في abcab. قبل البحث، أنشئ جدولًا lps، حيث تكون lps[i] طول أطول حافة في needle[0..i]. بالنسبة إلى abcabd، تكون قيمته [0, 0, 0, 1, 2, 0]. يعتمد الجدول على سلسلة البحث وحدها، وتبنيه باستخدام حلقة المطابقة نفسها، مع تشغيلها على سلسلة البحث بمقارنتها بنفسها.

بعد ذلك، امسح النص مرة واحدة واحتفظ بـ k، وهو عدد أحرف سلسلة البحث التي طابقت حتى الآن. إذا كان الحرف التالي مساويًا لـ needle[k]، فزد k بمقدار واحد. وإذا لم يكن كذلك، فاضبط k على lps[k-1] وقارن الحرف نفسه مرة أخرى، إلى أن يتطابق أو تصبح قيمة k مساوية لـ 0. إن الرجوع إلى حافة لا يتجاوز أي نسخة؛ فأي نسخة تبدأ داخل المحاولة الفاشلة لا بد أن تبدأ بحافة من الجزء الذي تمت مطابقته، وتُجرَّب أطول حافة أولًا. عندما تصل k إلى m، تكون النسخة قد بدأت عند i-m+1.

سبب كون هذه العملية خطية: تزداد k بمقدار واحد على الأكثر لكل حرف في النص، وكل رجوع يخفضها. ولا يمكن أن تنخفض مرات أكثر من عدد مرات ارتفاعها، لذا يستغرق المسح 2n خطوة على الأكثر، ويستغرق بناء الجدول 2m خطوة على الأكثر.

الخوارزمية

أنشئ lps: مع k = 0، ولكل i من 1 إلى m-1، ارجع إلى قيمة سابقة باستخدام k = lps[k-1] ما دام k > 0 وneedle[i] لا يطابق needle[k]؛ إذا تطابقا، فزد k؛ ثم خزّن lps[i] = k.
أعِد ضبط k إلى 0 وامسح سلسلة haystack باستخدام الفهرس i.
ما دام k > 0 وhaystack[i] لا يطابق needle[k]، فعيّن k = lps[k-1].
إذا كان haystack[i] يساوي needle[k]، فزد k.
إذا كان k يساوي m، فأعِد i-m+1. وإذا انتهت الحلقة، فأعِد -1.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

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

تقع معظم الأخطاء في نهاية النص أو داخل حلقة التراجع.

السماح لمؤشر البداية بالوصول إلى n-1 بدلًا من n-m. عندما يطابق طرف النص بداية النمط، تتجاوز المقارنة نهاية haystack، ما يؤدي إلى توقف Python وJava وRust وSwift بسبب خطأ في الفهرسة.
نسيان أن النمط قد يكون أطول من النص. مع الأطوال غير الموقعة، مثل size_t في C++ أو usize في Rust، لا يمكن أن تكون n-m سالبة: يلتفّ C++ بها إلى عدد هائل، ويحدث Rust ذعرًا في بنية التصحيح. تحقّق أولًا مما إذا كان m > n، أو أجرِ الحساب باستخدام أعداد صحيحة موقّعة.
كتابة التراجع في KMP على شكل if بدلًا من while. عند البحث عن aaa في aabaa، يحتاج b إلى تراجعين، من 2 إلى 1 ثم إلى 0. إذا توقفت بعد تراجع واحد، فستظل قيمة k تساوي 1 مع أن b لا يطابق شيئًا، وستُبلغ عن وجود تطابق عند الفهرس 2 غير موجود.
إرجاع مؤشر النص إلى الخلف بعد عدم التطابق في KMP. الذي يتغير فقط هو k. إعادة i إلى الخلف تعيد الحالة الأسوأ ذات التعقيد O(n · m).
إرجاع موضع نهاية التطابق أو فهرس يبدأ من 1. الإجابة هي موضع البداية، ويُحسب ابتداءً من 0. تبدأ السلاسل في Lua وR من 1، لذا اطرح 1 قبل الإرجاع.
تعريف strStr في المستوى الأعلى في PHP. أسماء الدوال في PHP لا تميّز بين الأحرف الكبيرة والصغيرة، لذا يتعارض هذا الاسم مع الدالة المضمّنة strstr. لهذا السبب، يضع القالب الابتدائي لـ PHP الدالة في مساحة أسماء خاصة بها.

أسئلة شائعة3

ما التعقيد الزمني لإيجاد أول ظهور لسلسلة نصية؟

يستغرق فحص كل موضع بداية زمنًا قدره O(n · m) في أسوأ الحالات، حيث يمثّل n وm طولي السلسلة haystack والإبرة، ويستخدم مساحة إضافية قدرها O(1). تستغرق خوارزمية Knuth-Morris-Pratt زمنًا قدره O(n + m) ومساحة قدرها O(m) لجدولها، مهما كانت الأحرف.

كيف يعمل جدول البادئات في KMP؟

لكل بادئة من نمط البحث، يخزّن الجدول طول أطول بادئة حقيقية منها تكون أيضًا لاحقة. بعد عدم التطابق مع مطابقة k أحرف، تكون هذه الأحرف الـk بادئةً من نمط البحث، وتبيّن lps[k-1] عدد الأحرف التي يمكن أن تبدأ النسخة المحتملة التالية. بالنسبة إلى aabaaab، يكون الجدول [0, 1, 0, 1, 2, 2, 3].

لماذا لا تستخدم find أو indexOf المضمّنتين؟

في كود الإنتاج، ينبغي لك ذلك، لأنه مُختبَر وسريع. يطرح المحاورون هذه المسألة ليروا كيف تكتب حلقة المطابقة بحدود صحيحة، ويسأل سؤال المتابعة المعتاد عن كيفية تجنّب الحالة الأسوأ O(n · m). تعتمد الحالة الأسوأ لعملية البحث المضمّنة على اللغة وإصدار المكتبة، لذا فهي لا تجيب عن سؤال المتابعة هذا.

def strStr(haystack, needle):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

haystack = "bananarama"
needle = "ana"

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