פראידוליה היא התופעה שבה העיניים נוטות לראות תבניות מוכרות בתמונות שבהן הן אינן קיימות באמת, למשל לראות פנים בענן. כפי שאפשר לדמיין, מכיוון ש-Farmer John נמצא תמיד בקרבת פרות, הוא רואה לעיתים קרובות תבניות הקשורות לפרות בחפצים יומיומיים. לדוגמה, כשהוא מביט במחרוזת "bqessiyexbesszieb", עיניו מתעלמות מחלק מהאותיות והוא רואה רק "bessiebessie".

בהינתן מחרוזת $s$, נסמן ב-$B(s)$ את מספר העותקים החוזרים המרבי של "bessie" שאפשר ליצור באמצעות מחיקת אפס או יותר תווים מ-$s$. בדוגמה לעיל, $B(\texttt{bqessiyexbesszieb}) = 2$.

חישוב $B(s)$ הוא אתגר מעניין, אבל Farmer John רוצה לפתור אתגר מעניין עוד יותר: בהינתן מחרוזת $t$ באורך לכל היותר $3\cdot 10^5$ המורכבת רק מהתווים a-z, חשבו את סכום $B(s)$ על פני כל תתי־המחרוזות הרציפות $s$ של $t$.

קלט

הקלט מכיל מחרוזת לא ריקה באורך לכל היותר $3\cdot 10^5$, שכל תוויה הם אותיות אנגליות קטנות.

פלט

הדפיסו מספר יחיד: המספר הכולל של עותקי "bessie" שאפשר ליצור על פני כל תתי־המחרוזות של מחרוזת הקלט.

דוגמאות

קלט 1

bessiebessie

פלט 1

14

הערה

שתים עשרה תתי־מחרוזות מכילות בדיוק עותק אחד של "bessie", ומחרוזת אחת מכילה בדיוק שני עותקים של "bessie", ולכן הסכום הוא $12\cdot 1 + 1 \cdot 2 = 14$.

קלט 2

abcdefghssijebessie

פלט 2

28

תתי־משימות

• קלטים 3-5: אורך המחרוזת הוא לכל היותר $5000$.
• קלטים 6-12: אין מגבלות נוספות.

מחברי הבעיה: Brandon Wang ו-Benjamin Qi