لدى Farmer John رسالة سرية يريد إخفاءها عن أبقاره؛ هي سلسلة طولها اثنان على الأقل وتحتوي فقط على الأحرف A..Z.
لتشفير الرسالة يطبق FJ سلسلة من «العمليات». تقصر العملية السلسلة $S$ أولًا بحذف أول حرف أو آخر حرف منها، ثم تلحق السلسلة الأصلية $S$ بالبداية أو النهاية. مثلًا، قد تعطي عملية واحدة على ABCD أربع سلاسل:
BCDABCD ABCABCD ABCDABC ABCDBCD
عند إعطاء السلسلة المشفرة النهائية، احسب عدد الطرق التي يمكن أن يكون FJ قد أنتجها بها بتطبيق عملية واحدة أو أكثر تباعًا على سلسلة أصلية ما. تعد العمليات مختلفة حتى إن أعطت التشفير نفسه. مثلًا، توجد أربع طرق مختلفة للحصول على AAA من AA، تقابل العمليات الأربع أعلاه.
الإدخال
- السطر $1$: سلسلة طولها لا يتجاوز 100.
الإخراج
- السطر $1$: عدد الطرق المختلفة لإنتاج هذه السلسلة بتطبيق عملية واحدة أو أكثر تباعًا على سلسلة أصلية طولها اثنان على الأقل. إذا لم توجد أي طريقة، اطبع صفرًا.
أمثلة
الإدخال 1
ABABA
الإخراج 1
6
ملاحظة
فيما يلي الطرق المختلفة لإنتاج ABABA:
- البدء بالسلسلة:
ABA -> AB+ABA - البدء بالسلسلة:
ABA -> ABA+BA - البدء بالسلسلة:
AB -> AB+A -> AB+ABA - البدء بالسلسلة:
AB -> AB+A -> ABA+BA - البدء بالسلسلة:
BA -> A+BA -> AB+ABA - البدء بالسلسلة:
BA -> A+BA -> ABA+BA
مؤلفا المسألة: Brian Dean وLewin Gan