class Solution:

    # @param S, a string
    # @param L, a list of string
    # @return a list of integer

    def __init__(self, S, L):
        self.S = S
        self.L = L
    def findSubstring(self, S, L):
        res = []      # result list
        num = len(L)  # length of the str list
        ls = len(S)
        if num == 0:
            return []
        str_len = len(L[0]) # length of each str

        #creating the map: counting the occurrence of each string

        map_str = dict((x,L.count(x)) for x in set(L))
        i = 0
        while i + num * str_len - 1 < ls:
            map_str2 = {}
            j = 0
            while j < num:
                subs = S[i + j * str_len:i + j * str_len + str_len ]
                if not subs in map_str:
                    break
                else:

                    map_str2[subs] = map_str2.get(subs, 0) + 1
                    if map_str2[subs]>map_str[subs]:
                        break
                    j = j + 1
            if j == num:
                res.append(i)
            i = i + 1

        return res

S = "barfoothefoobarman"
L = ["bar","foo"]

index = Solution(S, L)
print(index.findSubstring(S, L))

S = "barfoobarthefoobarman"
L = ["bar","foo"]
output = [0, 9]

S = "lingmindraboofooowingdingbarrwingmonkeypoundcake"
L = ["fooo","barr","wing","ding","wing"]
output = [13]