from collections import defaultdict

class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not s or not words:
            return []
        location = []

        wordsCount = defaultdict(int)
        for w in words:
            wordsCount[w] += 1

        wl = len(words[0])
        for i in range(wl):
            left, j, cnt = i, i, 0
            tempWordsCount = defaultdict(int)
            while j <= len(s) - wl:
                w = s[j:j+wl]
                if w in wordsCount:
                    tempWordsCount[w] += 1
                    if tempWordsCount[w] <= wordsCount[w]:
                        cnt += 1
                    else:
                        while tempWordsCount[w] > wordsCount[w]:
                            ww = s[left:left+wl]
                            tempWordsCount[ww] -= 1
                            if tempWordsCount[ww] < wordsCount[ww]:
                                cnt -= 1
                            left += wl
                    if cnt == len(words):
                        location += [left]
                        tempWordsCount[s[left:left+wl]] -= 1
                        cnt -= 1
                        left += wl
                else:
                    tempWordsCount.clear()
                    cnt = 0
                    left = j + wl
                j += wl
        return location