Zbalansowane słowa
면접 대비시간 제한3초메모리 제한1024 MB
길이가 300000 이하이고 a, b, c로만 이루어진 문자열이 주어질 때, 등장하는 모든 문자가 같은 횟수로 나타나는 비어 있지 않은 부분 문자열의 개수를 센다.
문제
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.