Anagram Suffixes
A software company is developing a new text editor. They want to highlight words that are anagrams of each other and appear as suffixes of the same string. Given a string S, find the number of pairs of indices (i, j) such that i < j and the suffix of S starting at index i is an anagram of the suffix of S starting at index j.
For example, in 'banana', the suffixes are 'banana', 'anana', 'nana', 'ana', 'na', 'a'. The suffix 'ana' starting at index 1 and the suffix 'ana' starting at index 3 are anagrams of each other.
Input
A single line containing the string S.
Output
A single integer representing the count of such pairs.
Constraints
1 <= |S| <= 200000, S consists of lowercase English letters.
Example 1
banana
0
Suffixes 'ana' (index 1) and 'ana' (index 3) are anagrams. Suffixes 'na' (index 2) and 'na' (index 4) are anagrams. Total 2 pairs.
Example 2
aaaa
0
All suffixes are anagrams of each other. 'aaaa', 'aaa', 'aa', 'a'. Pairs are (0,1), (0,2), (0,3), (1,2), (1,3), (2,3). Total 6 pairs.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
banana
aaaa