Problem
تريد كلوي أن تكتب رسالة إلى صديقتها. حرف - سلسلة تتكون من أحرف لاتينية صغيرة.
لسوء الحظ ، بمجرد أن بدأت كلوي في كتابة الرسالة ، أدركت أنها كانت طويلة جدًا وأن الأمر سيستغرق وقتًا طويلاً لكتابتها بالكامل. لذا فهي تريد كتابة نسخة مضغوطة من السلسلة النصية بدلاً من السلسلة نفسها.
نسخة مضغوطة من السلسلة s & [مدش]؛ تسلسل السلاسل c
1 ، & thinsp؛ s
1 ، & thinsp؛ c
2 ، & thinsp؛ s
2 ، & thinsp؛ ...، & thinsp؛ c
k ، & thinsp؛ s
k ، حيث c
i & mdash؛ التمثيل العشري لـ
i (بدون الأصفار البادئة) و s
i & mdash؛ بعض السلاسل من الأحرف اللاتينية الصغيرة. إذا كتب كلوي السلسلة s
1 بالضبط
1 مرة ، ثم s
2 بالضبط
2 مرات ، وهكذا في ، سينتج السلسلة s.
طول النسخة المضغوطة هو | c
1 | & thinsp؛ + & thinsp؛ | s
1 | & thinsp؛ + & thinsp؛ | c
2 | & thinsp؛ + & thinsp؛ | s
2 | ... | c
k | & thinsp؛ + & thinsp؛ | s
k |. من بين جميع الإصدارات المضغوطة ، يريد Chloe اختيار الإصدار الأقصر طولًا. ساعد كلوي في العثور على أقصر طول ممكن.
الإدخال:
يحتوي السطر الفردي للإدخال على سلسلة تتكون من أحرف لاتينية صغيرة (1 & thinsp؛ & le؛ & thinsp؛ | s | & thinsp؛ & le؛ & thinsp؛ 5000).
الإخراج:
طباعة عدد صحيح واحد و [مدش] ؛ الحد الأدنى لطول النسخة المضغوطة من السلسلة s.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
| aaaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
التفسيرات:
في المثال الأول ، سيختار كلوي الإصدار التالي: c 1 & mdash؛ 10، s 1 & [مدش]؛ أ.
في المثال الثاني ، سيختار كلوي الإصدار التالي: c 1 & mdash؛ 1، s 1 & [مدش]؛ abcab
في المثال الثالث ، سيختار Chloe الإصدار التالي: c 1 & mdash؛ 2، s 1 & [مدش]؛ c، c 2 & mdash؛ 1، s 2 & [مدش]؛ z، c 3 & mdash؛ 4، s 3 & [مدش]؛ أب.
نبسب ؛