Problem description
W Bajtocji niedługo wybory. Bajtek ma już dość słuchania przemówień, w których politycy ciągle powtarzają nazwiska przeciwników. Ostatnie przemówienie przedstawiciela Bajtockiej Zjednoczonej Partii Informatyków. podniosło mu ciśnienie: polityk ten w zasadzie ciągle powtarzał to samo. Bajtek zapisał sobie transkrypt przemówienia i chciałby policzyć ile jest w nim powtórzeń. Dokładniej, interesuje go liczba różnych spójnych podsłów przemówienia, które występują w nim co najmniej trzy razy. Pomożesz?
Napisz program, który: wczyta transkrypt przemówienia, wyznaczy liczbę różnych spójnych jego fragmentów, które występują w przemówieniu co najmniej trzykrotnie i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter alfabetu angielskiego (bez żadnych odstępów) – treść przemówienia polityka.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba różnych spójnych fragmentów przemówienia, które wystąpiły w nim co najmniej trzykrotnie.
Ograniczenia
Długość przemówienia nie przekracza 500 000 znaków.
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
W tym przypadku powtarzające się
fragmenty przemówienia to: |