405827: GYM102129 I Incomparable Pairs
Memory Limit:0 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
I. Incomparable Pairstime limit per test3 secondsmemory limit per test512 mebibytesinputstandard inputoutputstandard output
You are given a string s = s1s2... sn. Consider an unordered pair of its substrings {a, b}. Let us call such pair incomparable if neither a is a substring of b nor b is a substring of a. You have to compute the number of incomparable pairs of substrings of s.
InputThe first line of input contains a single string s consisting of lowercase English letters (1 ≤ |s| ≤ 105).
OutputOutput a single integer which is the answer to the problem.
ExamplesInputabbaOutput
8Input
abacabaOutput
64