26692번 - Zbalansowane słowa 다국어

Wszędzie najważniejsza jest równowaga. Jest ona szczególnie ważna przy organizacji konkursów programistycznych i mamy nadzieję, że jury tegorocznych Potyczek Algorytmicznych dobrze o tym wie.

Powiemy, że słowo jest zbalansowane, jeśli każda litera, która w nim występuje, występuje w nim tyle samo razy. Np. słowa w, mama, potyczki i aabbcbcccbaa są zbalansowane, podczas gdy słowa oko, algorytmistrz i abcba nie są. Mając dane długie słowo składające się jedynie ze znaków a, b oraz c, policz, ile jego niepustych podsłów (czyli spójnych przedziałów liter) jest zbalansowanych.

Uwaga: Dwa takie same słowa, występujące jako podsłowa na różnych pozycjach, liczymy wielokrotnie. Np. w słowie oko zbalansowanymi podsłowami są o, k, o, ok oraz ko.

W pierwszym wierszu wejścia znajduje się niepuste słowo, o długości nieprzekraczającej 300 000, składające się jedynie ze znaków a, b oraz c.

Na wyjściu powinna znaleźć się jedna liczba całkowita, oznaczająca liczbę zbalansowanych podsłów wejściowego słowa.

Wyjaśnienie przykładu: Zbalansowanymi podsłowami są: a, aa, aabb, aabbab, aabbabccc, ab, abba, abc, b, ba, bb, bc, c, cb, cba, cc, ccc. Zwróć uwagę, że niektóre z nich występują kilkukrotnie.