8457번 - Prefikso-sufiksy 다국어

Prefikso-sufiksem danego słowa w nazywamy słowo v, które jest zarówno prefiksem (początkowym fragmentem), jak i sufiksem (końcowym fragmentem) w. Prefikso-sufiksem właściwym w jest każdy jego prefikso-sufiks, który jest niepusty i krótszy od w. Niech PS(w) oznacza liczbę właściwych prefikso-sufiksów słowa w. Przez w[i, j] oznaczamy podsłowo słowa w zaczynające się na pozycji i i kończące się na pozycji j. Pozycje numerujemy od 1.

Dane jest słowo w. Twoim zadaniem jest wyznaczenie łącznej liczby właściwych prefikso-sufiksów wszystkich podsłów w, czyli obliczenie wyrażenia

\[\sum_{1 \le i \le j \le \left|w\right|}{PS\left(w\left[i, j\right]\right)}\text{.}\]

W pierwszym i jedynym wierszu wejścia znajduje się słowo w, składające się z co najmniej 1 i co najwyżej 10⁵ znaków. W słowie występują jedynie małe litery alfabetu angielskiego.

Na wyjściu należy wypisać sumaryczną liczbę właściwych prefikso-sufiksów wszystkich podsłów w.