ל־Farmer John יש הודעה סודית שהוא רוצה להסתיר מפרותיו: מחרוזת באורך לפחות 2 המכילה רק תווים A..Z.
להצפנה FJ מבצע רצף ״פעולות״. פעולה על $S$ קודם מקצרת אותה במחיקת התוו הראשון או האחרון, ואז מחברת את המחרוזת המקורית $S$ בתחילת המחרוזת או בסופה. למשל, פעולה אחת על ABCD יכולה לתת ארבע מחרוזות:
BCDABCD ABCABCD ABCDABC ABCDBCD
בהינתן המחרוזת המוצפנת הסופית, ספרו את מספר הדרכים שבהן FJ יכול היה ליצור אותה באמצעות פעולה אחת או יותר ברצף על מחרוזת מקור כלשהי. פעולות נחשבות שונות גם אם הן נותנות את אותה הצפנה. למשל, יש ארבע דרכים שונות לקבל AAA מ־AA, בהתאמה לארבע הפעולות לעיל.
קלט
- שורה $1$: מחרוזת שאורכה לכל היותר 100.
פלט
- שורה $1$: מספר הדרכים השונות ליצור מחרוזת זו בפעולה אחת או יותר ברצף על מחרוזת מקור כלשהי באורך לפחות 2. אם אין דרכים כאלה, הדפיסו אפס.
דוגמאות
קלט 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