from collections import defaultdict
def find_anagrams(a,b):

  # if length string b is greater than the length of string a,
  # return an empty list
  if len(b) > len(a): 
    return []

  # list to store the output, i.e., start indexes of all anagrams of string b in string a
  ans = []
  
  # create the hash maps
  hash_a = defaultdict(int) 
  hash_b = defaultdict(int) 

  # populate hash_b with the count of characters in string b 
  for i in range(len(b)):
    hash_b[b[i]] += 1

  # traverse string a: in each iteration, move the window rightward by one character
  for window_end in range(len(a)):
    
    # to move the window rightward, add a new element in it, i.e., 
    # add this new element and its count in the hash map, hash_a
    hash_a[a[window_end]] += 1

    # if the length of the sliding window exceeds the length of string b, 
    # make it equal to the length of string b by removing the left most element from the window, i.e.,
    # remove the left most element from the hash map, hash_a
    if window_end >= len(b):

      # index of the left-most element in the sliding window
      window_start = window_end - len(b)

      # if the count of left-most element is 1, it means it is safe to delete it from the hash map, hash_a               
      if hash_a[a[window_start]] == 1:
        del hash_a[a[window_start]]

      # if the count is greater than 1, then just remove one occurence of it from the hash map, hash_a
      else:
        hash_a[a[window_start]] -= 1

    # if the count of characters in hash_a equals the hash_b, we got the anagram, 
    # so append its start index to the output list
    if hash_a == hash_b:
      start_index = window_end - len(b) + 1
      ans.append(start_index) 

  return ans

# driver code
def main():
  A = ["abab", "cbaebabacd", "cefecf", "hello", "bro"]
  B = ["ab", "abc", "efc", "olleh", "bro"]
  for i in range(len(A)):
    print(i + 1, ".\tString a: \"", A[i], "\"", sep = "")
    print("\tString b: \"", B[i], "\"", sep = "")
    print("\tAnagrams of string b start at index(es) ", find_anagrams(A[i],B[i]), " in string a.", sep = "")
    print("-" * 100)

if __name__ == '__main__':
  main()