بالنظر إلى كلمة، قم بتحويلها إلى متناظر مع الحد الأدنى من إضافة الأحرف إليها [مغلق]

Question

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

مغلق منذ 7 سنوات.

هنا هو سؤال مقابلة مثيرة للاهتمام جدا:

بالنظر إلى كلمة واحدة ، قم بإلحاق أقل عدد من الأحرف بها لتحويلها إلى متناظر.

على سبيل المثال ، إذا كانت "مرحبا" هي السلسلة المعطاة ، فيجب أن تكون النتيجة "هيلوله."إذا أعطيت" كوكو "، يجب أن تكون النتيجة " كوكوك."

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

Answer 1

أولا جعل وظيفة لاختبار سلسلة ل متناظرة نيس ، مع الأخذ في الاعتبار أن "أ" و "آ" هي متناظرة.هم متناظرة, حق???

إذا كان الإدخال هو متناظرة ، إعادته (0 حرف تحتاج إلى أن تضاف) حلقة من س [طول] وصولا الى س [1] التحقق مما إذا كانت مجموعة فرعية من سلسلة س[أنا]..س [طول] هو متناظرة ، للعثور على أطول متناظرة.

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

كوكو = > ج + أوكو = > ج + أوكو + ج

مميب = > ممي + ع = > ممي + ع + إمم

Answer 2

حسنا!ها هي محاولتي الثانية.

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

HELLO
    O

1010
 010

3202
 202

1001
1001

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

وقت تشغيل هذه الخوارزمية هو وقت تشغيل بحث كمب القياسية بالإضافة إلى الوقت اللازم لعكس السلسلة:س (ن) + س (ن) = س (ن).

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

   | original string | | extra characters |

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

   | original string | | extra characters |
           | overlap |

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

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

نأمل أن يساعد هذا!

Answer 3

للإجابة أود أن أتخذ هذا النهج الساذج:

1. عندما نحتاج 0 الشخصيات?عندما سلسلة انها متناظرة
2. عندما نحتاج 1 حرف?عندما باستثناء سلسلة الأحرف الأولى هي متناظرة
3. عندما نحتاج 2 الشخصيات?عندما باستثناء الأحرف 2 بداية السلسلة هي متناظرة
4. الخ الخ...

لذلك يمكن أن تكون الخوارزمية

  for index from 1 to length
   if string.right(index) is palindrome
    return string + reverse(string.left(index))
   end
  next

تحرير

أنا لست كثيرا رجل الثعبان ، ولكن تنفيذ بسيط التفكير من التعليمات البرمجية الزائفة أعلاه يمكن أن يكون

>>> def rev(s): return s[::-1]
... 
>>> def pal(s): return s==rev(s)
... 
>>> def mpal(s):
...  for i in range(0,len(s)):
...   if pal(s[i:]): return s+rev(s[:i])
... 
>>> mpal("cdefedcba")
'cdefedcbabcdefedc'
>>> pal(mpal("cdefedcba"))
True

Answer 4

حل الوقت الخطي البسيط.

دعونا ندعو لدينا سلسلة س.

دع و (س, ص) يكون طول أطول بادئة مشتركة لـ س و ص.حساب و (ق [0], القس(ق)), و(ق[1], القس(ق)),...أين س [ك] هي لاحقة س بدءا من الموضع ك.من الواضح أنك تريد اختيار الحد الأدنى ك مثل ذلك ك + و(ق[ك] ، القس(ق)) = لين(ق).هذا يعني أنه عليك فقط إلحاق الأحرف ك في النهاية.إذا ك هو 0 ، اللدغة هي بالفعل متناظرة.إذا ك = لين (ق) ، فأنت بحاجة إلى إلحاق العكس بأكمله.

نحن بحاجة إلى حساب و (ق [أنا] ، ص) لجميع ق [أنا] بسرعة.هذا هو الجزء الصعب.إنشاء شجرة لاحقة من س.اجتياز الشجرة وتحديث كل عقدة مع طول أطول بادئة مشتركة مع ص.القيم في الأوراق تتوافق مع و (ق [أنا] ، ص).