عد palindromes مزدوجة في تسلسل int معين

Question

بالنسبة إلى عدد متسلسل معين ، فإن عدد palindromes المزدوجة ، حيث نعني عن طريق palindrome المزدوج تسلسل اثنين من palindromes نفسها دون كسر بينهما. على سبيل المثال:

في 1 0 1 1 0 1 لدينا 1 0 1 كقصور يظهر مرتين بدون استراحة ،

في 1 0 1 5 1 0 1 لدينا 1 0 1 ولكن تم فصله

(بصرف النظر عن palindromes الأخرى في هذه التسلسلات)

مثال المشكلة على مثال اختبار بيانات:

3

12 0 1 1 0 0 1 1 0 0 1 1 0

12 1 0 1 0 1 0 1 0 1 0 1 0

6 3 3 3 3 3 3

مع إجابات

8 0 9

Manacher واضح للتسول ، لكنني لست متأكدًا مما يجب فعله بعد ذلك. أي أفكار موضع تقدير. يجب أن يكون التعقيد أدناه n^2 أعتقد.

تحرير: int يعامل هنا كعنصر واحد من الأبجدية

Answer 1

نظرًا لأنك تعرف بالفعل خوارزمية للعثور على جميع palindromes (التي تكون راجع للشغل رائعة) ، كل ما عليك فعله هو ما يلي. لاحظ أن "palindrome المزدوج" هو أيضا palindrome:
عكس (pp) = عكسي (ع) عكسي (ع) = pp.

لذلك من بين كل palindromes (a,b) تجد (حيث بواسطة (a,b) أعني palindrome من الموقف a إلى موقع b)، تحتاج لتجد (i,j,k) مثل ذلك (i,j), (j,k), ، و (i,k) كلها باليندروم ، و j-i=k-j. على ما يعادل ، لكل palindrome (i,j) تجد ، تحتاج فقط إلى ضبط k = 2j-i, وتحقق من كليهما (k,j) و (i,k) هي palindromes.

إذا كانت الخطوة الأولى تُرجع m palindromes في المجموع ، فهذا يستغرق وقتًا (M)²) في أسوأ الأحوال. أعتقد أن هذا يجب أن يكون الأمثل في أسوأ الحالات (ضع في اعتبارك سلسلة من كل 1s).

Answer 2

سأبدأ بمجموعتين:

• مجموعة من تسلسل "النمو"
• مجموعة من تسلسل "تقلص"

الخوارزمية تعمل مثل هذا:

• في البداية كلا المجموعتين فارغة
• التعامل مع قيم المتجه واحد تلو الآخر ، افترض أننا نبحث الآن في القيمة الخامس
• حلقة على كل تسلسل "النمو"
  • إذا كانت القيمة الأخيرة للتسلسل المتزايد تساوي V ، فقم بنسخ التسلسل المتزايد إلى مجموعة التسلسلات المتقلصة ، قم بإزالة V من نهاية تسلسل تقلص جديد
  • إذا كانت القيمة الواحدة للتسلسل المتزايد تساوي V ، فقم بنسخ التسلسل المتزايد إلى مجموعة التسلسلات المتقلصة ، قم بإزالة العناصر الأخيرة (V والأخير) من تسلسل تقلص
• حلقة على كل تسلسل "تقلص"
  • إذا كانت القيمة الأخيرة لتسلسل تقلص تساوي V ، فقم بإزالتها من تسلسل تقلص. إذا أصبح تسلسل تقلص فارغًا ، فقد وجدنا palindrome.
  • إذا كانت القيمة الأخيرة للتسلسل المتقلص لا تساوي V ، فقم بحذف هذا التسلسل المتقلص
• أخيرًا ، قم بعمل تسلسل نمو جديد يتكون من V فقط

في الواقع ، تكون التسلسلات المتنامية عبارة عن تسلسلات قد تصبح palindrome مرة واحدة ، في حين أن تسلسل تقلص "جزئيًا" عبارة عن palindrome.