أطول مقطع بلا رموز مكررة: آخر ظهور وحد بداية لا يرجع

مقطع متصل تختلف رموزه

نريد أطول جزء متصل من سلسلة رموز لا يتكرر فيه رمز. نحافظ على الترتيب الأصلي، ولا نحذف حروفًا داخل الجزء كي نزيل تكرارها، لأن ذلك سيصنع تتابعًا جزئيًا مختلفًا. يمكن للرمز أن يتكرر في النص كله؛ الشرط يتعلق بالمقطع الذي اخترناه، بحيث تكون وحداته داخله مختلفة وفق معيار المساواة الذي حددناه.

تعرض مسألة CSES المسماة Playlist سؤال أطول تسلسل متصل من هويات مختلفة، ويشرح دليل USACO فكرة النافذة بمؤشرين يتحركان في الاتجاه نفسه. سنستعمل رموزًا نصية مؤلفة، ونحفظ آخر موضع لكل رمز وحد بداية لا يرجع إلى اليسار. لا ننقل أمثلة المصادر أو كودها، ولا نقدم أرقامنا بوصفها تشغيلًا في منصة المسابقة أو قياس أداء عليها.

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

تعريف تسلسل الهويات الفريدة، مرجع النافذة وحركات الحدود.

تسعة رموز وشاهدان بطول خمسة

نختار النص ABCADEAFG، ونرقم مواضعه من صفر إلى ثمانية. توجد A في المواضع صفر وثلاثة وستة، بينما B و C و D و E و F و G تظهر مرة في هذا المثال. المقطع BCADE عند [1,6) يحمل خمسة رموز مختلفة، ولا يضم A الأولى أو A عند الموضع ستة. كل حد يخص نسخة النص التي كتبناها بهذا الترتيب.

يوجد شاهد آخر DEAFG عند [4,9)، وطوله خمسة أيضًا. كلاهما متصل، وفي كل واحد منهما نسخة واحدة من A. لم نجمع رموزًا متفرقة من الشاهدين في جزء جديد، ولم نمنع A من جميع النوافذ لأنها تكررت في النص الكلي. نحتاج هذا الفصل كي لا يتحول فحص التكرار إلى حذف عالمي للرموز بدل اختيار مقطع صالح.

تنفيذنا يحتفظ بالشاهد الأول عند تساوي الطول الأفضل، لذلك يعرض BCADE وحدوده من واحد إلى ما قبل ستة. وجود هذه النتيجة لا يثبت أن الشاهد الوحيد هو BCADE، كما أن ظهور DEAFG لاحقًا لا يجعل الطول السابق خطأ. الصورة الرئيسية تعرض النص وموضعي الشاهدين، مع توضيح أنهما مثالان لطول أكبر تحققنا منه بتعداد مستقل.

آخر موضع قد يكون خارج النافذة

نحفظ خريطة تربط كل رمز بآخر موضع رأيناه في الجزء المعالج من النص. هذه الخريطة قد تحمل رمزًا آخر ظهوره قبل حد النافذة الحالي. وجوده في الخريطة لا يعني أنه يسبب تكرارًا داخل الجزء الذي نحتفظ به الآن؛ نراجع موضعه بالنسبة إلى الحد الأيسر قبل تقرير كيف يتحرك هذا الحد.

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

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

لماذا يحافظ الحد الجديد على الفرادة؟

نفترض أن النافذة السابقة كانت بلا تكرار. عند إضافة رمز واحد من اليمين، لا ينشأ تكرار جديد إلا مع نسخة من الرمز نفسه داخل هذه النافذة. إذا كان آخر ظهوره فيها عند الموضع p، فإن أي مقطع ينتهي في الرمز الحالي ويبدأ قبل p زائد واحد سيحتوي النسختين، فلا يكون صالحًا. تقديم البداية إلى ما بعد p يزيل هذا التعارض.

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

وهذه البداية هي أقرب بداية مسموحة إلى اليسار ضمن ما عالجناه لهذه النهاية؛ البداية الأقدم إما تخالف تعارضًا حفظناه سابقًا أو تدخل النسخة الجديدة المتكررة. لذلك طول النافذة هو الأكبر الصالح الذي ينتهي في الموضع الحالي. نراجع الأفضل بين هذه النهايات لنحصل على طول أكبر في النص كله، بدل التخمين من رمز تكرر مرات كثيرة في الأصل.

من ABC إلى BCADE

نقرأ A ثم B ثم C في المواضع صفر وواحد واثنين. لا يوجد ظهور سابق للرمزين الجديدين، فتظل البداية صفرًا وتزداد الأطوال إلى واحد واثنين وثلاثة. عند A التالية في الموضع ثلاثة نجد ظهورها السابق صفرًا داخل النافذة، فنقدم البداية إلى واحد. صار المقطع BCA عند [1,4)، بطول ثلاثة دون تكرار.

تأتي D عند أربعة، وهي جديدة في تاريخ القراءة، فتبقى البداية واحدًا ويصير المقطع BCAD بطول أربعة. ثم تأتي E عند خمسة، فتصير BCADE بطول خمسة. نحفظ الحدين واحدًا وستة بوصفهما أفضل شاهد حتى الآن، مع تذكر أن ستة حد توقف بعد آخر رمز دخل المقطع، وليس موضع E الذي يحمل الفهرس خمسة.

لم نعد البداية إلى صفر عندما ظهرت D أو E جديدتان، لأن ذلك سيدخل A الأولى مع A الثانية. الجديد من جهة اليمين لا يلغي سبب حذف بادئة سابقة. سجل كل مرحلة يحتفظ بالبداية قبل الإضافة وبعدها والظهور السابق والطول الحالي والأفضل، كي يظهر هذا الفرق ولا يبدو أن شرط عدم التكرار يطبق على الرمز الأخير منفردًا.

نافذة حالية أقصر وأفضل محفوظ

عند A في الموضع ستة، نجد آخر ظهور لها عند ثلاثة. البداية الحالية واحد، فننتقل إلى أربعة لأن ثلاثة زائد واحد أكبر منها. النافذة الحالية DEA عند [4,7)، وطولها ثلاثة. هذه خطوة صحيحة رغم أنها تقلل الطول الحالي من خمسة؛ أزلنا جزءًا يحتوي نسخة A القديمة، لكن لم نفقد حقيقة أن BCADE كانت شاهدًا صالحًا سابقًا.

نضيف F عند سبعة فتصبح DEAF بطول أربعة، ثم G عند ثمانية فتصبح DEAFG بطول خمسة. يتساوى هذا الطول مع الأفضل المحفوظ، فلا يستبدل التنفيذ شاهد BCADE في سياسة التحسن الصارم. نهاية النص تحمل نافذة مختلفة من أفضل الشاهد المعروض، لكن كليهما بطول خمسة عند هذه المرحلة وله حدود معروفة.

إذا عرضنا الطول الحالي وحده في مرحلة A عند ستة، لكان الرقم ثلاثة لا يمثل أفضل ما رأيناه في جميع النص المعالج. لذلك نحفظ متغيرين لهما معنى مختلف: طول النافذة الصالحة الآن، وأفضل طول بين النهايات السابقة والحالية. لا نطلب أن يتزايد الأول دائمًا، بينما الثاني لا ينقص عند إضافة رموز جديدة إلى النص في هذه المهمة.

مثال قد يعيد البداية خطأ

نختار النص QRRSTQ. تبدأ النافذة بـ Q ثم R، لكن R الثانية في الموضع اثنين تكرر R عند واحد، فتنتقل البداية إلى اثنين. بعد S و T تكون النافذة RST عند [2,5). عندما تأتي Q الأخيرة عند خمسة، نجد ظهورها السابق صفرًا، وهو خارج النافذة الحالية لأنه أقدم من بدايتها اثنين.

إذا كتبنا البداية مباشرة بوصفها الموضع السابق زائد واحد، ستصبح واحدًا بدل اثنين. سيدخل عندئذ المقطع RRSTQ عند [1,6)، وهو يحمل R مرتين، وقد يبدو طوله خمسة نتيجة أفضل لكنها غير صالحة. نستعمل الأكبر بين البداية الحالية اثنين والمرشح واحد، فتبقى البداية اثنين، ويكون الشاهد RSTQ بطول أربعة.

الصورة الثانية تفصل الظهور القديم من الحد الحالي، وتعرض ما يدخل النافذة إذا سمحنا لها بالرجوع. هذا مثال مؤلف لسبب الحماية، لا مجرد نصيحة باستعمال دالة الأكبر دون تفسير. اختبرنا الشاهد الصحيح والخاطئ مباشرة من المصدر، فحقق الصحيح عدد رموز مختلفًا مساويًا طوله، وفشل الآخر بسبب النسختين المتجاورتين من R.

عرض الرسم بالحجم الكامل

حدث الظهور حتى حين لا يتحرك اليسار

في QRRSTQ، لم تحرك Q الأخيرة البداية لأنها ظهرت قديمًا خارج النافذة، لكن ينبغي تحديث آخر موضع لها إلى خمسة. إذا أضفنا Q أخرى بعد ذلك، فظهورها السابق الحقيقي داخل النافذة عند خمسة، ونحتاج تقديم البداية إلى ستة. حفظ الصفر القديم بدل الخمسة سيجعل الفحص يتجاهل التكرار الجديد ويقبل جزءًا يحمل Q مرتين.

لذلك الخريطة تسجل آخر ظهور في جميع الرموز التي قرأناها، لا آخر ظهور فقط عندما أُجبرنا على تغيير الحد. قرار التحريك وسجل الظهور خطوتان مختلفتان. وقد تبقى في الخريطة رموز خرجت من النافذة، مع بقاء معلوماتها مفيدة إذا ظهرت مرة أخرى؛ نراجع موقعها وقت الاستعمال بدل حذف معناها أو افتراض أنها ما زالت موجودة داخل النافذة.

الخريطة وحدها لا تعرض كل مواضع كل رمز أو عدد ظهوره الإجمالي؛ تحفظ موضعًا أخيرًا لكل مفتاح. أثر القراءة الذي أخرجناه يحتوي معلومات إضافية عن الخطوات السابقة، لكن لا نخلط هذه المعلومات بحقل الموضع الأخير. عند بناء مخرج أخف يكتفي بالطول والشاهد، نحدد ما الذي نريد الاحتفاظ به للمراجعة وما الذي يمكن حذفه من الأثر.

التعادل وطول الشاهد وحدوده

في المثال الأول يحتفظ تنفيذنا بالحدين [1,6) عندما تصل BCADE إلى خمسة، ويتركهما عند DEAFG ذات الطول نفسه. السياسة تفضل أول ظهور للطول الأفضل أثناء التقدم في النهايات. لا تقول إن الشاهد المختار أصغر أبجديًا في كل نص أو إنه أفضل معنى أو إن الشواهد الأخرى غير صحيحة.

نراجع الحدين بإعادة المقطع من النص، ثم نقارن طوله بالفرق بين التوقف والبداية، ونقارن عدد رموزه المختلفة بهذا الطول. هذه ثلاث مراجعات تربط الرقم بالموضع وبشرط الفرادة. إذا كان الشاهد قد كتب بعد فرز الرموز أو حذف أحدها، فلن تكفي فرادة الناتج الجديد لإثبات أنه مقطع متصل من الأصل.

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

الفراغ والتكرار الكامل والرموز الجديدة

النص الفارغ يعطينا طولًا صفرًا وشاهدًا فارغًا وحدين صفر وصفر في تنفيذ الفحص. لا يوجد مقطع غير فارغ نختاره، وهذه حالة بداية معرفّة. وإذا كان النص AAAA، فأكبر طول واحد، لأن أي مقطع أطول سيحتوي A مرتين. نحتفظ بأول A وفق سياسة التعادل التي شرحناها، ولا نعامل كون النص كله مكررًا سببًا لرفض المدخل.

أما ABCDE، فرموزه مختلفة، ويكون النص كله شاهدًا بطول خمسة. كل مرحلة تمد النافذة دون تحريك اليسار. وفي AA نراجع أن الظهور السابق للرمز الثاني هو صفر، وأنه يوجب نقل البداية إلى واحد. هذا يختبر الفرق بين عدم وجود ظهور سابق وبين وجوده في الموضع الأول، وهي حالة قد يفسدها استعمال قيمة الرقم بوصفها اختبار وجود.

ومثال Aa يحمل رمزين مختلفين في المساواة الحرفية التي اخترناها. إذا وحدنا حالة الأحرف قبل الحساب فسيصبح عقدًا آخر وقد يتغير الطول. لا نقرر أن اختلاف الحرفين أو مساواتهما هو الصحيح لكل استخدام؛ نحدد كيفية التعرف على الهوية في النص الذي عالجناه، ثم نربط الشاهد بهذه النسخة بدل تفسير الرقم بلا سياسة مساواة معلنة.

الاتصال يختلف من إزالة التكرار

في ABCADEAFG، يمكن أن نجمع الرموز المختلفة في مجموعة فنجد A و B و C و D و E و F و G، وعددها سبعة. هذا لا يثبت مقطعًا متصلًا بطول سبعة بلا تكرار في الأصل. عملية المجموعة تجاهلت المواضع والاتصال، بينما سؤالنا يحتاج جميع رموز المقطع بين حدين دون حذف رموز داخله أو إعادة ترتيبها.

وكذلك قد ينتج حذف نسخ A المتكررة سلسلة أطول تبدو فريدة، لكنها لم تعد مقطعًا من الأصل. لا نحرر النص كي نجعل نتيجة الشرط ممكنة؛ نبحث عن أفضل جزء يحققه كما ورد. وإذا كانت المهمة تقطيع ملف إلى نوافذ ثابتة مع تداخل أو ربط نوافذ بمدخلاتها، فإنها تسأل عن حدود ومصدر آخرين، لا عن أكبر طول فريد الذي حسبناه هنا.

لا نستعمل طريقة مجموع نافذة موجبة أيضًا، لأن معيار الصلاحية هنا تكرار الهويات، وليس قيمة عددية نجمعها. قد يملك رمز شكلًا عدديًا مثل 0 ويظل رمزًا صالحًا في هذا العقد. ما يحرك اليسار هو موضع نسخة سابقة من الرمز داخل النافذة، لا كون قيمة آخر مدخل أكبر من هدف أو كونه موجبًا في مسألة أخرى.

وحدة الرمز ونسخة النص

نقصر الشرح على رموز لاتينية واضحة في نص عادي، ويقارن تنفيذنا وحداته كما قدمت دون تحويل أو حذف. مدخل غير نصي يرفض بدل تحويله تلقائيًا إلى سلسلة تمثيل لا نعرف هل يوافق السؤال. إذا أردنا قائمة معرفات أغنيات أو عناصر أخرى، يمكن تعريف واجهة مناسبة لهوياتها، لكن نسخة الدالة التي نفذناها لها عقد نصي محدد.

في نصوص طبيعية أكثر تعقيدًا، يحتاج صاحب المهمة إلى تحديد وحدة الرمز: وحدة برمجية أو كتابة مرئية أو كلمة أو معرف. لا تقدم أمثلة A و R معيارًا لتقطيع كل نص عربي أو تجميع أشكال حروفه، ولا تقيس جودة مرمز لغوي. نثبت المساواة والوحدة والتحويلات قبل تفسير شرط غير مكرر على مخرج برنامج.

وإضافة رمز إلى النهاية قد تغير النافذة الحالية أو تزيد أفضل طول، لكنها لا تجعل فهارس نسخة قديمة تتبع ملفًا عدلناه في وسطه تلقائيًا. نحفظ النص الذي حسبنا منه، وحدود الشاهد، وسياسة الهوية والتعادل. بهذه البيانات يمكن للمراجع إعادة المقطع وفحص فرادته، ومعرفة متى يجب بناء نتيجة جديدة بعد تعديل الأصل أو طريقة التعرف على الرمز.

حركة واحدة إلى اليمين وحفظ إضافي

نقرأ كل رمز مرة، ونحدث موضعه الأخير، ونراجع حد البداية والطول. الحد الأيسر لا يرجع إلى الخلف، وقد يقفز أكثر من موضع حين يتكرر رمز داخل النافذة. هذا يبين عدد مراحل المرور البسيط في تنفيذنا، دون أن نحتاج اختبار كل مقطع كامل عند كل نهاية. شرح المصدر للنافذة بمؤشرين يساعد على تمييز هذه الحركة من طريقة طرفين تبدأ من جهتين مختلفتين.

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

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

مرجع كل المقاطع القصيرة

راجعنا 3280 نصًا من رموز A و B و C بأطوال من صفر إلى سبعة. المرجع المستقل يولد كل زوج بداية وتوقف، ويقبل المقطع إذا ساوى عدد رموزه المختلفة طوله، ثم يختار الأكبر مع أول شاهد عند التعادل. قارنّا الحدين والطول والشاهد بنتيجة خريطة آخر ظهور، لا بالطول وحده الذي قد يخفي شاهدًا يحمل تكرارًا.

وراجعنا 21324 مرحلة بادئة من حيث فرادة النافذة الحالية وأفضل طول في النص المعالج والموضع السابق الصحيح وتقدم اليسار. جربنا كذلك المثالين المؤلفين وحدود الفراغ والتكرار وحالة الحروف والموضع صفر، وإضافة Q جديدة بعد ظهور خارج النافذة. هذه فحوص محدودة وليست برهانًا تجريبيًا لكل مدخل أو قياس جودة لغة أو أداء على منصة المصادر.

قبل قبول نتيجة جديدة، ثبت وحدة الهوية وشرط الاتصال، ثم راجع آخر ظهور بالنسبة إلى البداية الحالية، واستخرج الشاهد من حدود الأصل. تحقق من الفرادة والطول وسياسة التعادل، ولا تسمح لظهور قديم خارج النافذة أن يرجع حدها. ستعرف حينها لماذا يبقى الأفضل محفوظًا مع نافذة حالية أقصر، وما الذي تقوله خريطة آخر ظهور وما الذي يحتاج سجلًا أو سؤالًا آخر.