دالة البادئة: البداية والنهاية قد تتداخلان

الخلاصة السريعة

أطول بداية من ABABA تساوي نهاية له، دون أخذ النص كله، هي ABA وطولها 3. البداية تشغل المواضع 0 و 1 و 2، والنهاية 2 و 3 و 4؛ الموضع 2 مشترك. قيم دالة البادئة للنص هي 0 و 0 و 1 و 2 و 3. وفي ABABABA يظهر النمط ABABA عند البدايتين 0 و 2، إذا حسبنا الظهور المتداخل.

• دالة البادئة عند موضع معين تعطي طول أطول بداية للجزء المنتهي هناك تكون نهاية له أيضًا، مع استبعاد الجزء كله من الاختيار. قيمة الموضع الأول 0. [1]
• في ABABA تتساوى ABA الأولى والأخيرة بطول 3، وتشتركان في الموضع 2. لا نطلب فصل البداية والنهاية مكانيًا؛ اختيار A بطول 1 صحيح بوصفه تطابقًا، لكنه ليس الأطول.
• للأجزاء A و AB و ABA و ABAB و ABABA، القيم بالترتيب 0 و 0 و 1 و 2 و 3. العدد طول، وليس رقم بداية أو نهاية؛ القيمة 3 تخص الجزء الكامل المنتهي عند الموضع 4.
• في النص ABABABA، النوافذ ذات الطول 5 تبدأ عند 0 و 1 و 2. الأولى والثالثة ABABA، والوسطى BABAB؛ إذن البدايتان المطابقتان 0 و 2، أو الموضعان الأول والثالث عند العد من 1.
• النص الكامل ABABA بطول 5 مستبعد من حساب دالة البادئة، رغم مساواته لنفسه. الصفر يعني غياب تطابق غير فارغ بالشروط، لا غياب الحروف. بعد تغيير آخر حرف إلى C يصبح أطول تطابق لـ ABABC بطول 0؛ وفي ABaBA بحرف a صغير يكون الطول 1 وفق المقارنة الحرفية.
• الأمثلة تقارن أحرفًا لاتينية محددة كما كتبت، بترقيم يبدأ من 0، وتعد الظهور المتداخل. لا نستنتج من هذه الحسابات قاعدة لمقارنة الكتابة العربية أو وعدًا بسرعة برنامج؛ ولا نخلط طول البداية المشتركة بعدد مرات ظهور النمط.

حدد البداية والنهاية، واستبعد النص كله

البادئة جزء يبدأ من أول النص، واللاحقة جزء ينتهي عند آخره. في دالة البادئة نبحث، لكل جزء ينتهي عند موضع محدد، عن أطول بادئة تساوي لاحقة له، لكنها لا تساوي الجزء كله. نكتب 0 إذا لم يوجد تطابق غير فارغ؛ وعند الموضع الأول تكون القيمة 0. [1]

نستخدم ABABA، وترتيب أحرفه من اليسار إلى اليمين A ثم B ثم A ثم B ثم A. نرقمها 0 و 1 و 2 و 3 و 4. هذا ترقيم مواضع، أما طول النص فهو 5. لا نقرأ الحروف معكوسة لمجرد أن الشرح مكتوب بالعربية.

مثلًا،ABA في البداية تقع عند 0 و 1 و 2. و ABA في النهاية تقع عند 2 و 3 و 4. الأجزاء هنا متجاورة الأحرف داخل كل جزء؛ لا نحذف حرفًا من الوسط كي نحصل على مساواة. نثبت هذه القواعد قبل عد الأطوال.

لا تصلح ABABA نفسها جوابًا بطول 5، لأننا استبعدنا الجزء الكامل. من دون هذا القيد سيختار كل نص نفسه دائمًا، ولن يوضح الحساب الجزء الأقصر الذي تتقاسمه بدايته ونهايته.

لماذا تكون ABA بطول 3 هي الجواب؟

نختبر الأطوال الأقصر من 5. عند الطول 4، البداية ABAB والنهاية BABA مختلفتان؛ أول حرف A في الأولى و B في الثانية. عند الطول 3، البداية ABA والنهاية ABA متساويتان حرفًا حرفًا.

عند الطول 2 نقارن AB بـ BA، فتفشل المساواة. وعند الطول 1 نجد A في الطرفين، فتنجح. إذن الأطوال الموجبة المقبولة هنا 1 و 3، وأكبرها 3. اختيار A وحدها يفوّت تطابق ABA الأطول.

تغطي ABA الأولى المواضع 0 إلى 2، والثانية 2 إلى 4. يشارك الحرف A عند 2 في الجزأين. لم نقل إن الجزأين يجب أن يحتلا مواضع منفصلة، لذلك لا نقسم طول النص على 2 لفرض حد مصطنع على الجواب.

الصورة الرئيسية تعرض النص نفسه مرة في كل سطر، مع تلوين البداية في سطر والنهاية في آخر. الخط عند الموضع 2 يبين اشتراكهما. السطران ليسا نصين جديدين أو نسختين يجب لصقهما؛ إنهما عرضان للأحرف الخمسة نفسها.

احسب قيمة لكل جزء من البداية حتى الموضع الحالي

لدالة البادئة خمس قيم هنا، واحدة لكل موضع. الجزء المنتهي عند 0 هو A، وعند 1 هو AB، وعند 2 هو ABA، وعند 3 هو ABAB، وعند 4 هو ABABA. لا نحسب خمسة نصوص مستقلة تبدأ من مواضع مختلفة؛ كلها تبدأ عند 0.

في A لا يوجد اختيار غير فارغ أقصر من الجزء كله، فتكون القيمة 0. في AB لا تتساوى A الأولى مع B الأخيرة، فتكون القيمة 0 أيضًا. لا يعني الصفر أن النص فارغ؛ يعبر عن غياب تطابق غير فارغ ضمن القيد.

في ABA تتساوى A الأولى والأخيرة، فالقيمة 1. في ABAB تتساوى AB الأولى والأخيرة بطول 2، بينما ABA الأولى تختلف عن BAB الأخيرة؛ القيمة 2. وفي ABABA حسبنا القيمة 3 من مقارنة ABA بطرفي النص.

يبين الجدول الجزء الذي فحصناه والتطابق الأطول وطوله. القيم 0 و 0 و 1 و 2 و 3 قائمة أطوال؛ لا نقول إن 3 هو موضع آخر حرف، لأن آخر حرف في ABABA يقع عند 4. ولا نحول هذه القيم مباشرة إلى عدد مرات ظهور النص.

ظهور النمط مرتين يمكن أن يشارك بعض الأحرف

في مسألة أخرى نبحث عن ABABA داخل ABABABA. نعد كل ظهور كامل، حتى لو تداخل مع ظهور آخر. طول النمط 5، وطول النص 7؛ تبدأ النوافذ الكاملة الممكنة عند 0 أو 1 أو 2 فقط.

النافذة عند 0 تضم المواضع 0 إلى 4، ونصها ABABA. النافذة عند 1 تضم 1 إلى 5، ونصها BABAB، فلا تطابق النمط. النافذة عند 2 تضم 2 إلى 6، ونصها ABABA، فتطابقه.

البدايتان إذن 0 و 2. الظهوران يشتركان في المواضع 2 و 3 و 4، ونصها ABA. لا نحذف الثاني لمجرد استعمال تلك المواضع في الأول، ما دام سؤالنا يطلب جميع الظهورات المتداخلة.

إذا اخترنا بدلًا من ذلك ظهورات لا تتشارك أي موضع، فلن نستطيع أخذ هذين الظهورين معًا. يختلف هذا الشرط عن سؤالنا الأصلي. وتظهر الصورة الداخلية المحاذاة نفسها: النص في الأعلى، ثم النمط عند 0، ثم عند 2؛ الفراغات وسيلة محاذاة لا أحرف داخل النص.

غيّر حرفًا أو اصطلاح العد، ثم راجع النتيجة

إذا غيرنا آخر حرف في ABABA إلى C، نحصل على ABABC. عند الأطوال 1 و 2 و 3 و 4 نقارن A مع C، و AB مع BC، و ABA مع ABC، و ABAB مع BABC. لا ينجح أي منها، فيكون الطول المطلوب 0؛ الجزء الكامل ذو الطول 5 ما زال مستبعدًا.

وإذا كتبنا ABaBA بحرف a صغير في الوسط، فإن ABA و aBA لا يتساويان في المقارنة الحرفية التي اخترناها. يبقى A عند الطرفين متساويًا؛ وتفشل الأطوال 2 و 3 و 4، فيكون الجواب 1. لا نحول a إلى A دون إعلان قاعدة جديدة للمقارنة.

عند ترقيم مواضع ABABABA من 1 بدل 0، تصبح بدايتا الظهور 1 و 3 بدل 0 و 2. الأحرف والظهوران لم يتغيرا، كما لم يتغير طول النمط 5. اذكر اصطلاح الترقيم عندما تسجل مواقع النتائج.

الأمثلة التعليمية تستخدم أحرفًا لاتينية بسيطة ومقارنة معلنة. لا تعالج تطبيع الكتابة أو التشكيل أو معنى كلمة في لغة طبيعية. والحساب اليدوي يوضح تعريف دالة البادئة والتداخل؛ لا يعرض تنفيذ خوارزمية KMP ولا يدعي زمنًا أو ذاكرة لبرنامج.