حل فئات غامضة في قائمة مرتبة

Question

ودعونا نأخذ مثالا ملموسا، وآمل أن يكون واضحا. لنفترض أن (أمر) قائمة أشهر:

<اقتباس فقرة>   

يناير <فبراير <مارس <... <   ديسمبر

و(مع الأعداد الصحيحة التي تقف لأشهر، الصفرية)، بحيث

<اقتباس فقرة>   

ويناير 0، فبراير هو 1، ...، ديسمبر هو 11.

والآن لنفترض أنني لم يكن لديك الوصول إلى الأسماء الكاملة أشهر، وأنا أعطيت القائمة التالية، حيث تم تقصير أشهر لأول رسالتهم، و<م> ه لتقف على فئة فارغة، مثل هذا:

<اقتباس فقرة>   

وه، F، ه، ه، ه

إذا كنت بناء قائمة "أشهر لا لبس فيها" (و: 1، ق: 8، س: 9، ن: 10، د: 11)، ويمكن ملء الفئات فارغة من قبل عن طريق حساب أولا الفئة الأولى (باستخدام الطرح وزارة الدفاع 12)، ومن ثم إرسال الباقي من هناك. ومع ذلك، لنفترض أنا أعطيت قائمة

<اقتباس فقرة>   

وه، A، ه، ه، ي، ه

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

وسؤالي، وأخيرا، هو: هل هناك حل التحليلي (وظيفة، خوارزمية) لهذه المشكلة، أو هو أملي الوحيد لاستخدام القوة الغاشمة لتحديد كل علاقة محتملة؟ لبعض الأمثلة، لا يمكن لتوضيح خوارزمية / وظيفة العمل: ينظر في الحالة التي لدي <م> J تليها 11 <م> ه الصورة، تليها <م> J تليها 11 <م> ه الصورة ... وبما أنه ليس هناك سنة في بين، وأنا لا يمكن إزالة الغموض <م> J في يناير، يونيو أو يوليو.

<القوي> الإجابة : لانتهى بي الأمر الترميز الجواب ايل بهيما، لأن لهذه الحالة على وجه الخصوص، والتعابير المنطقية لا بأس بها، حتى في أعلى O إدارة الوقت (بالمليون). ومع ذلك، وأنا قبلت الإجابة بن باعتبارها الجواب الصحيح لأنه يستوعب الآخرين (يذكر الحل التعابير المنطقية)، ولكن يشير أيضا أفضل طريقة باستخدام KMP خوارزمية O (م + ن)، على الرغم من أن هذا هو لأعداد أكبر من السلسلة ضد لتتناسب مع نمط. شكرا لكم جميعا.

Answer 1

ولست متأكدا إذا كان هذا هو بالضبط ما كنت أبحث عنه، ولكن هل يمكن استخدام تعديل <لأ href = "http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm" يختلط = "noreferrer نوفولو"> KMP سلسلة البحث خوارزمية لحل هذه المشكلة.

والتعديل سيكون لتتناسب مع أي شيء ضد فئة فارغة. حتى يمكن أن تجد جميع القيم الممكنة بالنسبة لك، مثل J مع 11 في البريد مثل التي ذكرتها.

ويمكنك أيضا استخدام آلة الدولة لتحديد الاحتمالات، وهذا هو ما < وأ href = "http://en.wikipedia.org/wiki/Regular_expression" يختلط = "نوفولو noreferrer"> التعبير العادية ستفعل.

Answer 2

وأسهل طريقة للقيام بذلك هو استخدام التعابير العادية. افترض أنك تريد أن تطابق e, A, e, e, J, e.

وبناء التعبير العادي التالي: r = ".A..J."

واسمحوا c تكون سلسلة سيطرتنا:

  c = "JFMAMJJASONDJFMAMJJASOND"

والآن نحن نبحث عن جميع مباريات r في c السلسلة حيث مؤشر انطلاق مباراة ضمن النصف الأول من c.

في عام، وهذا قد لا يكون الأسلوب الأكثر فعالية. الحل الأكثر السذاجة، في محاولة لتتناسب مع نمط مع كل تحول الدائري لل"JFMAMJJASOND" سلسلة السيطرة تدير في الوقت O(nm)، حيث n هو طول من نمط، m هو طول سلسلة التحكم (في حالتنا JFMAMJJASOND).

Answer 3

ويمكننا أن نبني على الجواب ايل بهيما وقليلا عن الحالة العامة. أولا، نحن ندرك أن أزواج فقط غامضة حقا من A، M، J أو هما J والتي هي ستة أشهر بعيدا أو اثنين من نفس الرسالة التي هي سنة على حدة. فإن أي تركيبة أخرى تسفر مباراة لا لبس فيها في سلسلة السيطرة. (لقد بنيت جدول كافة التركيبات الممكنة لإثبات ذلك.)

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