- قيد الملء
- يُقرأ منها
- الإجابة
أطول متتالية جزئية مشتركة (LCS)
ما الحروف المشتركة بين كلمتين بالترتيب نفسه؟ أطول متتالية جزئية مشتركة تجيب عن ذلك، وعليها تُبنى أدوات diff والمدققات الإملائية ومقارنات الحمض النووي. اكتب كلمتين وشاهد جدولًا من حروفهما يمتلئ، ثم تتبّع الإجابة رجوعًا من الزاوية. اضغط «تشغيل» لمشاهدة الجدول وهو يمتلئ، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. اكتب كلمتين: الأولى تمتد نزولًا على جانب الجدول، والثانية على طول أعلاه. تحمل كل خلية طول أطول متتالية جزئية مشتركة بين الحروف حتى صفها وعمودها. في النهاية تُقرأ الحروف رجوعًا بدءًا من الخلية السفلية اليمنى. «مثال جديد» يختار زوجًا آخر من الكلمات. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.
كيف يعمل
- اكتب كلمتين: الأولى تمتد نزولًا على جانب الجدول، والثانية على طول أعلاه.
- اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع.
- شاهد كل خلية وهي تقارن حرفيها، ثم اتبع المسار البرتقالي رجوعًا من الزاوية لقراءة الإجابة.
كيف يعمل الجدول
تحمل الخلية طول أطول متتالية جزئية مشتركة بين حروف الكلمة الأولى حتى صفها وحروف الكلمة الثانية حتى عمودها. يمثّل الصف والعمود المعلَّمان بـ – كلمة فارغة، لذا قيمتهما 0. إذا تساوى حرفا الخلية، كانت الخلية أكبر بواحد من الخلية أعلاها إلى اليسار. وإذا اختلفا، فأحد الحرفين ليس جزءًا من الإجابة، لذا تأخذ الخلية القيمة الأكبر من الخلية التي فوقها والخلية التي على يسارها.
قراءة الحروف رجوعًا
الخلية السفلية اليمنى هي طول الإجابة. لإيجاد الحروف، ابدأ من هناك: حيث يتطابق الحرفان، يكون ذلك الحرف ضمن المتتالية الجزئية، وتنتقل إلى أعلى اليسار؛ وإلا فتنتقل إلى الأكبر من الخلية التي فوقها والخلية التي على يسارها. الحروف التي تُجمع في الطريق، إذا قُرئت بترتيب معكوس، تشكّل أطول متتالية جزئية مشتركة. قد توجد متتاليات أخرى بالطول نفسه، والقراءة رجوعًا تجد إحداها.
الأسئلة المتداولة
ما الفرق بين المتتالية الجزئية والسلسلة الجزئية؟
السلسلة الجزئية حروف متجاورة متتابعة، مثل ACE في RACER. أما المتتالية الجزئية فتحافظ على الترتيب لكنها قد تتخطى حروفًا، لذا فإن ACE متتالية جزئية من ABCDE أيضًا. أطول سلسلة جزئية مشتركة مسألة مختلفة لها جدول مشابه.
ما مدى سرعة خوارزمية LCS؟
لكلمتين طولاهما m وn يحتوي الجدول على m·n خلية، تُملأ كل منها في خطوة واحدة، لذا فالعمل O(m·n). ولنصين في كل منهما 10,000 سطر يعني ذلك 100 مليون خلية، ولهذا تستخدم أدوات diff طرقًا أذكى مبنية على الفكرة نفسها.
هل أطول متتالية جزئية مشتركة وحيدة؟
لا. للكلمتين ABCBDAB وBDCABA ثلاث متتاليات جزئية مشتركة مختلفة طولها 4: BCBA وBCAB وBDAB. الجدول يعطي الطول، والقراءة رجوعًا تختار إحداها.
هل تبيّن LCS مدى تشابه كلمتين؟
جزئيًا. يمكن تحويل كلمتين طولاهما m وn، وطول أطول متتالية جزئية مشتركة بينهما k، إحداهما إلى الأخرى بحذف m − k حرفًا وإدراج n − k حرفًا. ومسافة التحرير، التي تسمح أيضًا باستبدال حرف، غالبًا ما تكون مقياسًا أفضل.
هل يُرسل أي شيء إلى أي مكان؟
لا. كل شيء يُحسب في متصفحك، وتبقى إعداداتك الأخيرة في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر