You want to form a target string of lowercase letters.
At the beginning, your sequence is target.length '?' marks.  You also have a stamp of lowercase letters.
On each turn, you may place the stamp over the sequence, and replace every letter in the sequence with the corresponding letter from the stamp.  You can make up to 10 * target.length turns.
For example, if the initial sequence is "?????", and your stamp is "abc",  then you may make "abc??", "?abc?", "??abc" in the first turn.  (Note that the stamp must be fully contained in the boundaries of the sequence in order to stamp.)
If the sequence is possible to stamp, then return an array of the index of the left-most letter being stamped at each turn.  If the sequence is not possible to stamp, return an empty array.
For example, if the sequence is "ababc", and the stamp is "abc", then we could return the answer [0, 2], corresponding to the moves "?????" -> "abc??" -> "ababc".
Also, if the sequence is possible to stamp, it is guaranteed it is possible to stamp within 10 * target.length moves.  Any answers specifying more than this number of moves will not be accepted.
 
Example 1:
Input: stamp = "abc", target = "ababc"
Output: [0,2]
([1,0,2] would also be accepted as an answer, as well as some other answers.)


Example 2:
Input: stamp = "abca", target = "aabcaca"
Output: [3,0,1]


 
Note:



1 <= stamp.length <= target.length <= 1000
stamp and target only contain lowercase letters.

Difficulty: interview

Starter code:

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        

Solutions:
'''
\"aabcaca\"
 0123456
  x
 
devide conquer
先找到第一个stamp把string分成左右两部分（必须要）（On
然后从长到短用stamp的头match左边的部分，直到match到最头 如果不能到最头则退出
从长到短用stamp的尾巴match右边，直到match到尾巴，如果不能match到最尾巴 则 继续找下一个stamp
能把他分成左右
这时的左边有个offset了，比如****b** offset是3，只要stamp的长度不超过头且能match上，就可以

这个解法可以有nwin*M^2 其中m平方是在用stamp去match的时候最坏能从stamp最长match到1
可以给出最短match路径


'''
class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        ans = []
        offset = 0
        while target!='':
            x = target.find(stamp)
            if x==-1:
                return []
            ans.append(x+offset)
            
            can_stamp,indices = self.moveLeft(stamp,target[:x],offset)
            if not can_stamp:
                return []
            ans.extend(indices)
            
            offset,target,indices = self.moveRight(stamp,target[x+len(stamp):],
                                                offset+x+len(stamp))
            ans.extend(indices)
            
        return ans[::-1]
        
        
    
    def moveLeft(self,stamp,s,offset):
        ans = []
        while s:
            for ind in range(1,len(stamp)):
                additional = 0
                if ind>len(s):
                    if offset == 0:
                        continue
                        
                    additional = ind - len(s)
                    
                if stamp[additional:ind]==s[-ind:]:
                    ans.append(offset+len(s)-ind)
                    s=s[:-ind]
                    break
            else:
                return False,[]
        return True,ans
        
    
    def moveRight(self,stamp,s,offset):
        ans = []
        while s:
            for ind in range(1,len(stamp)):
                if stamp[-ind:]==s[:ind]:
                    ans.append(offset+ind-len(stamp))
                    offset+=ind
                    s=s[ind:]
                    break
            else:
                return offset,s,ans
        return offset,s,ans


'''
\"aabcaca\"
 0123456
  x
 
devide conquer
先找到第一个stamp把string分成左右两部分（必须要）（On
然后从长到短用stamp的头match左边的部分，直到match到最头 如果不能到最头则退出
从长到短用stamp的尾巴match右边，直到match到尾巴，如果不能match到最尾巴 则 继续找下一个stamp
能把他分成左右
这时的左边有个offset了，比如****b** offset是3，只要stamp的长度

这个解法可以有nwin*M^2 其中m平方是在用stamp去match的时候最坏能从stamp最长match到1
可以给出最短match路径


'''
class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        ans = []
        offset = 0
        while target!='':
            x = target.find(stamp)
            if x==-1:
                return []
            ans.append(x+offset)
            
            can_stamp,indices = self.moveLeft(stamp,target[:x],offset)
            if not can_stamp:
                return []
            ans.extend(indices)
            
            offset,target,indices = self.moveRight(stamp,target[x+len(stamp):],
                                                offset+x+len(stamp))
            ans.extend(indices)
            
        return ans[::-1]
        
        
    
    def moveLeft(self,stamp,s,offset):
        ans = []
        while s:
            for ind in range(1,len(stamp)):
                additional = 0
                if ind>len(s):
                    if offset == 0:
                        continue
                        
                    additional = ind - len(s)
                    
                if stamp[additional:ind]==s[-ind:]:
                    ans.append(offset+len(s)-ind)
                    s=s[:-ind]
                    break
            else:
                return False,[]
        return True,ans
        
    
    def moveRight(self,stamp,s,offset):
        ans = []
        while s:
            for ind in range(1,len(stamp)):
                if stamp[-ind:]==s[:ind]:
                    ans.append(offset+ind-len(stamp))
                    offset+=ind
                    s=s[ind:]
                    break
            else:
                return offset,s,ans
        return offset,s,ans


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        stamp = list(stamp)
        target = list(target)
        result = []
        
        def change(i):
            if target[i:i + m].count('?') == m:
                return False
            ch = False
            for j in range(m):
                if target[i + j] == '?':
                    continue
                if target[i + j] != stamp[j]:
                    ch = False
                    break
                ch = True
            if ch:
                target[i:i + m] = ['?'] * m
                result.append(i)
            return ch
        ch = True
        while ch:
            ch = False
            for i in range(n - m + 1):
                ch |= change(i)
            
        return reversed(result) if target.count('?') == n else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        done = set()
        n = len(stamp)
        m = len(target)
        res = []
        
        def check(i):
            j = 0
            count = 0
            while j < n :
                if i in done:
                    j += 1
                    i += 1
                elif stamp[j] == target[i]:
                    count += 1
                    i += 1
                    j += 1
                else:
                    return False
            return count > 0
        
        while len(done) < m :
            found = 0
            for i in range(m-n+1):
                if check(i):
                    for j in range(i,i+n):
                        done.add(j)
                    res.append(i)
                    found = 1
                    break
            if not found:
                return []
                    
        
        
        
        
        return res[::-1]
                
            
        
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        #if not sol return []
        
        #start from target and trace back, use dfs each time change slice in stamp to ??? or ??X
        
        list_s, list_t = list(stamp), list(target)  #convert to list coz str immutable
        res = []
        
        #changed means if this round can remove stamp
        changed = True
        while changed:
            #记住先赋值false！！！
            changed = False
            #check each slice of target if can remove stamp!
            for i in range(len(list_t) - len(list_s) + 1):
                changed = changed or self.remove_stamp(list_s, list_t, i, res)

        return res[::-1] if list_t == ['?'] * len(list_t) else []
    
    
    def remove_stamp(self, list_s, list_t, i, res):
        #check if target can remove stamp from ind of i; if ? can also remove!!!!!!!(abc??-->ababc 反过来 ababc-->ab??? then ab? can still un-stamp!!!!)
        changed = False
    
        for j in range(len(list_s)):
            if list_t[i + j] == '?': 
                continue
            if list_t[i + j] != list_s[j]: 
                return False
            changed = True
        
        #also need convert target back!
        if changed:
            list_t[i:i + len(list_s)] = ['?'] * len(list_s)     #数组可以直接整体赋值！！！
            
            res.append(i)
            
        return changed

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:

        def canStamp(targetStr, idx, stamp):
            hasOneChar = False
            for i in range(len(stamp)):
                if targetStr[idx+i] == \"?\":
                    continue
                
                if targetStr[idx+i] == stamp[i]:
                    hasOneChar = True
                    continue
                else:
                    return False
            if hasOneChar:
                return True
            else:
                return False
            
        
        queue = [(target, [])]
        
        while queue:
            curtStr, steps = queue.pop(0)
            if len(steps) >= len(target) * 10:
                continue
            if all(x == \"?\" for x in list(curtStr)):
                return steps[::-1]
            for i in range(len(curtStr) - len(stamp) + 1):
                if canStamp(curtStr, i, stamp):
                    queue.append((curtStr[:i] + \"?\" * len(stamp) + curtStr[i+len(stamp):], steps + [i]))
                    break
            
            

from collections import deque

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        #if not sol return []
        
        #start from target and trace back, use dfs each time change slice in stamp to ??? or ??X
        
        list_s, list_t = list(stamp), list(target)
        res = []

        changed = True
        while changed:
            changed = False
            for i in range(len(list_t) - len(list_s) + 1):
                changed = changed or self.remove_stamp(list_s, list_t, i, res)

        return res[::-1] if list_t == ['?'] * len(list_t) else []
    
    
    def remove_stamp(self, list_s, list_t, i, res):
        changed = False
    
        for j in range(len(list_s)):
            if list_t[i + j] == '?': 
                continue
            if list_t[i + j] != list_s[j]: 
                return False
            changed = True
            
        if changed:
            list_t[i:i + len(list_s)] = ['?'] * len(list_s)
            
            res.append(i)
            
        return changed

# ababcbc
class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        s, t = list(stamp), list(target)
        ans = []
        
        def check(idx):
            changed = False
            for i in range(m):
                if t[idx + i] == \"?\": continue
                if t[idx + i] != s[i]: return False
                changed = True
            if changed:
                t[idx: idx + m] = [\"?\"] * m
                ans.append(idx)
            return changed
            
        changed = True
        while changed:
            changed = False
            for i in range(n - m + 1):
                if check(i):
                    changed = True
                    break
        return ans[::-1] if t == [\"?\"] * n else []
                

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # This is Greedy sol from https://leetcode.com/problems/stamping-the-sequence/discuss/189254/Python-Greedy-and-DFS
        # reversely change target to **********
        # the method is once find a substring in target that equals stamp, change them to *
        # when seeing a * just continue
        # continue doing this until no matching can be found
        
        def check(i):
            found = False
            for j in range(len(s)):
                if t[i+j] == '*':
                    continue
                if t[i+j] != s[j]: # substring t[i:i+m] != s
                    return False
                found = True
            if found:
                t[i:i+len(s)] = ['*'] * len(s)
                res.append(i)
            return found
        
        n, m, t, s, res = len(target), len(stamp), list(target), list(stamp), []
        while True:
            found = False
            for i in range(n-m+1):
                found = found or check(i)
            if not found:
                break
        return res[::-1] if t == ['*']*n else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        def one_sweep():
            nonlocal done, ans
            for ti in range(len(target) - len(stamp) + 1):
                matched_cs, matched = [], True
                for si in range(len(stamp)):
                    sc, tc = stamp[si], target[ti]
                    if ti in done:
                        ti = ti + 1
                        continue
                    elif sc == tc:
                        matched_cs.append(ti)
                        ti = ti + 1
                    else:
                        matched = False
                        break
                if matched and matched_cs:
                    done = done | set(matched_cs)
                    ans.append(ti - len(stamp))
                    return True                        
            return False
            
        ans, done = [], set()
        while one_sweep(): pass
        return ans[::-1] if len(done) == len(target) else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        n = len(target)
        m = len(stamp)
        seen = [0]*n
        t = list(target)
        total = 0
        def match(ind): # to match pattens in target
            l = 0
            size = 0
            while l <=m-1 and ind+l<=n-1:
                if t[ind+l] == stamp[l]:
                    l+=1
                    size += 1
                elif t[ind+l]=='*':
                    l+=1
                else:
                    return 0
            t[ind:ind+l] = ['*']*l
            return size
        ans = []
        while total<n:
            found = False
            for i in range(n-m+1):
                if seen[i]==0:
                    num = match(i)
                    if num>0:
                        found = True
                        seen[i]=1
                        total+= num
                        ans.append(i)
                        break
            if found == False:
                break
        return ans[::-1] if total==n else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        #if not sol return []
        
        #start from target and trace back, use dfs each time change slice in stamp to ??? or ??X
        
        list_s, list_t = list(stamp), list(target)  #convert to list coz str immutable
        res = []
        
        #changed means if this round can remove stamp
        changed = True
        while changed:
            #记住先赋值false！！！
            changed = False
            #check each slice of target if can remove stamp!
            for i in range(len(list_t) - len(list_s) + 1):
                changed = changed or self.remove_stamp(list_s, list_t, i, res)

        return res[::-1] if list_t == ['?'] * len(list_t) else []
    
    
    def remove_stamp(self, list_s, list_t, i, res):
        #check if target can remove stamp from ind of i; if ? can also remove!!!!!!!(abc??-->ababc 反过来 ababc-->ab??? then ab? can still un-stamp!!!!)
        #changed = False
    
        for j in range(len(list_s)):
            if list_t[i + j] == '?': 
                continue
            if list_t[i + j] != list_s[j]: 
                return False
        
        #also need convert target back!
        #first check if target already ??? case then no need change!!!!!!!
        if list_t[i:i + len(list_s)] != ['?'] * len(list_s):
            list_t[i:i + len(list_s)] = ['?'] * len(list_s)     #数组可以直接整体赋值！！！
            
            res.append(i)
            return True
        
        return False

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        done = set()
        n = len(stamp)
        m = len(target)
        candidates = { i for i in range(m-n+1) }
        res = []
        
        def check(i):
            j = 0
            count = 0
            while j < n :
                if i in done:
                    j += 1
                    i += 1
                elif stamp[j] == target[i]:
                    count += 1
                    i += 1
                    j += 1
                else:
                    return -1
            if count == 0:
                return 0
            else:
                return 1
        
        while len(done) < m :
            found = 0
            remove = set()
            for i in candidates:
                I = check(i)
                if I == 1:
                    for j in range(i,i+n):
                        done.add(j)
                    res.append(i)
                    found = 1
                    break
                elif I == 0:
                    remove.add(i)
                    
            if not found:
                return []
            else:
                candidates.remove(i)
                candidates -= remove
                
                    
        return res[::-1]
                
            
        
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        sLen = len(stamp)
        tLen = len(target)
        dp = {}
        # buttom up DP approach

        def dfs(sidx, tidx, result):
            \"\"\"
            1. stamp[sidx] == target[tidx], sidx+=1, tidx+=1
            2. stamp[sidx] != target[tidx], dp[sidx, tidx] = []
            3. sidx == sLen, stamp is done, backtrace
            4. end criteria, tidx == tLen, and sidx == sLen (stamp要蓋完)

            using sidx, tidx as key for DP
            \"\"\"

            if tidx == tLen:
                dp[sidx, tidx] = result if sidx == sLen else []

            if (sidx, tidx) not in dp:
                if sidx == sLen:
                    # backtracking

                    for idx in range(sLen):
                        dp[sidx, tidx] = dfs(idx, tidx, [tidx-idx] + result)

                        if dp[sidx, tidx]:
                            break

                elif stamp[sidx] == target[tidx]:
                    nextResult = dfs(sidx+1, tidx+1, result)
                    dp[sidx, tidx] = nextResult if nextResult else dfs(0, tidx+1, result + [tidx+1])

                else:
                    dp[sidx, tidx] = []

            return dp[sidx, tidx]

        return dfs(0, 0, [0])


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        if set(stamp) < set(target) or len(stamp) > len(target):
            return []
        
        path = []
        while target != '*' * len(target):
            prev_target = target
            for i in range(len(target) - len(stamp) + 1):
                if target[i:i + len(stamp)] == '*' * len(stamp):
                    continue
                if not all(target[i + j] in (stamp[j], '*') for j in range(len(stamp))):
                    continue
                
                target = target[:i] + '*' * len(stamp) + target[i + len(stamp):]
                path.append(i)
            
            if prev_target == target:
                return []
        
        return path[::-1]   

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        star = 0
        visited = [False]*len(target)
        target = list(target)
        res = []
        while star<len(target):
            doReplace = False
            for i in range(len(target)-len(stamp)+1):
                if not visited[i] and self.canReplace(stamp,target,i):
                    #if target[i:i+len(stamp)]==['*']*len(stamp):
                    #    visited[i] = True
                    #    continue
                    star+=self.doReplace(stamp,target,i)
                    doReplace = True
                    visited[i] = True
                    res.append(i)
                    if star==len(target):
                        break
            if not doReplace:
                return []
        return res[::-1]
    
    def canReplace(self, stamp:str,target:List[str],i:int) -> bool:
        for j in range(len(stamp)):
            if target[i]!='*' and stamp[j]!=target[i]:
                return False
            i+=1
        return True
    
    def doReplace(self,stamp:str,target:List[str],i:int) -> int:
        count = 0
        for j in range(len(stamp)):
            if target[i]!='*':
                target[i] = '*'
                count+=1
            i+=1
        return count

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        t = list(target)
        res = []
        
        def check(i):
            if t[i:i+m] == ['?']*m:
                return False
            
            for j in range(m):
                if t[i+j] not in  ['?', stamp[j]]:
                    return False
            
            t[i:i+m] = ['?']*m
            res.append(i)
            return True
        
        change = True
        while change:
            change = False
            for i in range(n-m+1):
                change |= check(i)
            
        return res[::-1] if t == ['?']*n else []
                
            
                


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        marks, t = 0, list(target)
        res = []
        visited = set()
        while marks < len(target):
            found = False
            for i in range(len(t) - len(stamp) + 1):
                if i not in visited and self.canReplace(stamp, t,i):  
                    marks += self.replace(stamp,t,i)
                    res.append(i)  
                    visited.add(i)  
                    found = True
                if marks >= len(target): break
            if not found: return []

        return res[::-1]
    
    def canReplace(self, s,t, j): 
        for i in range(len(s)):    
            if t[j+i] != \"*\" and s[i] != t[j+i]:                
                return False               
        return True
    
    def replace(self, s,t, j):
        count = 0
        for i in range(len(s)):
            if t[i+j] != \"*\":
                t[i+j] = \"*\"
                count += 1
        return count
        

class Solution(object):
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        memo = {}

        def dfs(t, s, cur_stmp):
            if (t, s) in memo:
                return memo[t, s]
            if s == len(stamp):
                if t < len(target):
                    # check if cur_stmp precedes its following substring
                    for i, ch in enumerate(stamp):
                        if ch == target[t]:
                            suffix_stmp_seq = dfs(t, i, t-i)
                            if suffix_stmp_seq:
                                memo[t, s] = suffix_stmp_seq + [cur_stmp]
                                return suffix_stmp_seq + [cur_stmp]
                    else:
                        memo[t, s] = []
                        return []
                else:
                    memo[t, s] = [cur_stmp]
                    return [cur_stmp]
            
            if t == len(target):
                # target[t] is empty while s < len(stamp), cur_stmp cannot succeeds empty.
                memo[t,s] = []
                return []

            if stamp[s] == target[t]:
                seq1 = dfs(t+1, s+1, cur_stmp)
                if seq1:
                    memo[t, s] = seq1
                    return seq1
                else:
                    cand = dfs(t+1, 0, t+1)
                    memo[t,s] = [cur_stmp] + cand if cand else []
                    return [cur_stmp] + cand if cand else []

            elif stamp[s] != target[t]:
                # check if cur_stmp succeeds the substring target[t:]
                if stamp[0] == target[t]:
                    suffix_stmp_seq = dfs(t, 0, t) 
                    memo[t, s] = [cur_stmp] + dfs(t, 0, t) if suffix_stmp_seq else []
                    return [cur_stmp] + dfs(t, 0, t) if suffix_stmp_seq else []
                else:
                    memo[t, s] = []
                    return []

        return dfs(0, 0, 0)

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        marks, t = 0, list(target)
        res = []
        visited = set()
        while marks < len(target):
            found = False
            for i in range(len(t) - len(stamp) + 1):
                if i not in visited and self.canReplace(stamp, t,i):  
                    marks += self.replace(stamp,t,i)
                    res.append(i)  
                    visited.add(i)  
                    found = True
                if marks >= len(target): break
            if not found: return []

        return res[::-1]
    
    def canReplace(self, s,t, j): 
        for i in range(len(s)):    
            if t[j+i] != \"*\" and s[i] != t[j+i]:                
                return False               
        return True
    
    def replace(self, s,t, j):
        count = 0
        for i in range(len(s)):
            if t[i+j] != \"*\":
                t[i+j] = \"*\"
                count += 1
        return count
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        l = len(stamp)
        
        @lru_cache(None)
        def dfs(i, o):
            if i == len(target):
                return []
            
            if not o:
                if i+l > len(target):
                    return None
                for k in range(l):
                    if i+k >= len(target) or stamp[k] != target[i+k]:
                        break
                    if dfs(i+k+1, False) is not None:
                        return [i] + dfs(i+k+1, False)
                else:
                    if dfs(i+k+1, True) is not None:
                        return dfs(i+k+1, True) + [i]
            else:
                for j in range(l):
                    if l-j+i > len(target):
                        continue
                    for k in range(j,l):
                        if i+k-j >= len(target) or stamp[k] != target[i+k-j]:
                            break
                        if dfs(i+k-j+1, False) is not None:
                            return [i-j] + dfs(i+k-j+1, False)
                    else:
                        if dfs(i+k-j+1, True) is not None:
                            return dfs(i+k-j+1, True) + [i-j]
            return None
            
        return dfs(0, False)
                


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        n, m = len(target), len(stamp)
        if n < m:
            return False

        def check_and_mark(s: list, i: int) -> tuple:
            # return True if update, next_read_pos
            if s[i:i+m] == ['?'] * m:
                return False, i + 1
            i0 = i
            j = 0
            while i < n and j < m and (s[i] == '?' or s[i] == stamp[j]):
                i += 1
                j += 1
            if j == m:
                s[i0:i0 + m] = ['?'] * m
                return True, i
            else:
                return False, (n if i == n else i0 + 1)
        
        final = ['?'] * n
        ans = []
        target = list(target)
        while target != final:
            i = 0
            updated = False
            while i < n:
                done, i = check_and_mark(target, i)
                if done:
                    updated = done
                    ans.append(i - m)
            if not updated:
                return []
        return ans[::-1]

def matchs(stamp, target, i, j, ans, pos):
        S = len(stamp)
        T = len(target)
        if (target[i] != stamp[j]) or (T - i < S - j) or (j > i):
            return False
            
        res = ['?'] * T 
        res[i - j : i - j + S] = list(stamp)
        for poss in range(pos, len(ans)):
            if ans[poss] in range(i - j - S + 1, i):
                res[ans[poss]: min(ans[poss] + S, T)] = list(stamp[:min(S, T - ans[poss])])
        
        res = \"\".join(res)
        if (res[i - j : i] == target[i - j : i]):
            return True
        else:
            return False
        
class Solution:            
    def movesToStamp(self, stamp: str, target: str):
        S = len(stamp)
        T = len(target)
        j = 0
        pos = -1
        ans = []
        for i in range(T):
            j = j % S
            if(target[i] == stamp[j]):
                if(j == 0):
                    reached = False
                    for j in range(S-1, 0, -1):
                        if matchs(stamp, target, i, j, ans, pos):
                            reached = True
                            ans.insert(pos, i - j)
                            break
                    if not reached:
                        if matchs(stamp, target, i, 0, ans, pos + 1):
                            j = 0
                            pos += 1
                            ans.insert(pos, i)
                        else:
                            return []
            else:
                reached = False
                if (j == 0):
                    for j in range(S-1, 0, -1):
                        if matchs(stamp, target, i, j, ans, pos):
                            reached = True
                            ans.insert(pos, i - j)
                            break
                else:
                    for j in range(S):
                        if matchs(stamp, target, i, j, ans, pos + 1):
                            reached = True
                            pos += 1
                            ans.insert(pos, i - j)
                            break
                if not reached:
                    return []
            j += 1
        return ans

                
                        
    
        
        

class Solution(object):
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        memo = {}
        T, S = len(target), len(stamp)
        def dfs(t, s, cur_stmp):
            if t == T:
                memo[t, s] = cur_stmp if s == S else []
                return memo[t, s]
            if (t, s) not in memo:
                # complete match, find successor
                if s == S:
                    for i in range(S):
                        if stamp[i] == target[t]:
                            suff_stmp = dfs(t, i, [t-i]) 
                            if suff_stmp:
                                memo[t, s] = suff_stmp + cur_stmp
                                break
                    else:
                        memo[t, s] = []

                elif stamp[s] == target[t]:
                    suff_stmp = dfs(t+1, s+1, cur_stmp)
                    if suff_stmp:
                        memo[t, s] = suff_stmp
                    else:
                        # add word cut and find predeccessor
                        suff_stmp = dfs(t+1, 0, [t+1])
                        memo[t, s] = cur_stmp + suff_stmp if suff_stmp else []

                else:
                    memo[t, s] = []

                return memo[t, s] if memo[t, s] else []


        return dfs(0, 0, [0])

class Solution(object):
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        memo = {}
        T, S = len(target), len(stamp)
        def dfs(t, s, cur_stmp):
            if t == T:
                memo[t, s] = cur_stmp if s == S else []
                return memo[t, s]
            if (t, s) not in memo:
                # complete match, find successor
                if s == S:
                    for i in range(S):
                        if stamp[i] == target[t]:
                            suff_stmp = dfs(t, i, [t-i]) 
                            if suff_stmp:
                                memo[t, s] = suff_stmp + cur_stmp
                                break
                    else:
                        memo[t, s] = []

                elif stamp[s] == target[t]:
                    suff_stmp = dfs(t+1, s+1, cur_stmp)
                    if suff_stmp:
                        memo[t, s] = suff_stmp
                    else:
                        # add word cut and find predeccessor
                        suff_stmp = dfs(t+1, 0, [t+1])
                        memo[t, s] = cur_stmp + suff_stmp if suff_stmp else []

                elif stamp[s] != target[t]:
                    # add word cut and find predeccessor
                    if stamp[0] == target[t]:
                        suff_stmp = dfs(t, 0, [t])
                        memo[t, s] = cur_stmp + suff_stmp if suff_stmp else []
                    else:
                        memo[t, s] = []

                return memo[t, s] if memo[t, s] else []


        return dfs(0, 0, [0])


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        stamp = list(stamp)
        target = list(target)
        res = []
        
        def check(i):
            changed = False
            for j in range(len(stamp)):
                if target[i+j] == '?': continue
                if target[i+j] != stamp[j]: return False
                changed = True

            return changed
            
        seen = [0] * len(target)   
        ans = True
        while ans:
            ans = False
            for i in range(len(target) - len(stamp) + 1):
                changed = check(i)               
                ans = ans or changed
                            
                if changed:
                    res.append(i)
                    target[i:i+len(stamp)] = ['?'] * len(stamp)
                    seen[i:i+len(stamp)] = [1] * len(stamp)
                               
        return res[::-1] if sum(seen) == len(target) else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        from collections import deque
        m, n = len(stamp), len(target)
        queue = deque()
        done = [False]*n
        ans = []
        A = []
        for i in range(n-m+1):
            todo, made = set(), set()
            for j in range(m):
                if stamp[j] == target[i+j]:
                    made.add(i+j)
                else:
                    todo.add(i+j)
            A.append((todo, made))
            if not todo:
                ans.append(i)
                for j in made:
                    if not done[j]:
                        done[j] = True
                        queue.append(j)
        while queue:
            i = queue.popleft()
            for j in range(max(0, i-m+1), min(i, n-m)+1):
                if i in A[j][0]:
                    A[j][0].discard(i)
                    if not A[j][0]:
                        ans.append(j)
                        for k in A[j][1]:
                            if not done[k]:
                                done[k] = True
                                queue.append(k)
                                
        return ans[::-1] if all(done) else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        ls,lt = list(stamp),list(target)
        m,n = len(ls),len(lt)
        todo,move,res = n-m+1,0,[]
        def match(lst,ls):
            ret = False
            for c1,c2 in zip(lst,ls):
                if c1 == '?':
                    continue
                elif c1 != c2:
                    return False
                else:
                    ret = True
            if ret:
                lt[i:i+m] = ['?']*m
            return ret
        while move<todo:
            prv = move
            for i in range(n-m+1):
                if match(lt[i:i+m],ls):
                    move += 1
                    res.append(i)
            if lt == ['?']*n:return res[::-1]
            if prv == move:break
        return []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        N, M, match = len(target), len(stamp), True
        
        positions = []
        while match:
            match, idx = False, 0
            while idx <= N-M:
                match_cnt = 0
                for i in range(M):
                    if target[idx+i] == '?':
                        continue
                    if target[idx+i] != stamp[i]:
                        break
                    match_cnt += 1
                else:
                    if match_cnt:
                        positions.append(idx)
                        target = target[:idx] + '?'*M + target[idx+M:]
                        match, idx = True, idx+M-1
                idx += 1
        return positions[::-1] if target == '?'*N else []


class Solution(object):
    def movesToStamp(self, stamp, target):
        M, N = len(stamp), len(target)

        queue = collections.deque()
        done = [False] * N
        ans = []
        A = []
        for i in range(N - M + 1):
            # For each window [i, i+M),
            # A[i] will contain info on what needs to change
            # before we can reverse stamp at i.

            made, todo = set(), set()
            for j, c in enumerate(stamp):
                a = target[i+j]
                if a == c:
                    made.add(i+j)
                else:
                    todo.add(i+j)
            A.append((made, todo))

            # If we can reverse stamp at i immediately,
            # enqueue letters from this window.
            if not todo:
                ans.append(i)
                for j in range(i, i + len(stamp)):
                    if not done[j]:
                        queue.append(j)
                        done[j] = True

        # For each enqueued letter,
        while queue:
            i = queue.popleft()

            # For each window that is potentially affected,
            # j: start of window
            for j in range(max(0, i-M+1), min(N-M, i)+1):
                if i in A[j][1]:  # This window is affected
                    A[j][1].discard(i) # Remove it from todo list of this window
                    if not A[j][1]:  # Todo list of this window is empty
                        ans.append(j)
                        for m in A[j][0]: # For each letter to potentially enqueue,
                            if not done[m]:
                                queue.append(m)
                                done[m] = True

        return ans[::-1] if all(done) else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        done = [False]*n
        from collections import deque
        ans = []
        queue = deque()
        A = []
        for i in range(n-m+1):
            todo, made = set(), set()
            for j, ch in enumerate(stamp):
                a = target[i+j]
                if a == ch:
                    made.add(i+j)
                else:
                    todo.add(i+j)
            A.append((made, todo))
            if not todo:
                ans.append(i)
                for k in made:
                    if not done[k]:
                        done[k] = True
                        queue.append(k)
        
        while queue:
            i = queue.popleft()
            for j in range(max(0, i-m+1), min(i, n-m)+1):
                if i in A[j][1]:
                    A[j][1].discard(i)
                    if not A[j][1]:
                        ans.append(j)
                        for k in A[j][0]:
                            if not done[k]:
                                done[k] = True
                                queue.append(k)
        return ans[::-1] if all(done) else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        #
        # BFS & DP ----- Time Limit Exceeded
        # -----------------------------------------------------------------------------------------------
        # n = len(target)
        # k = len(stamp)
        # visited = set()
        # q = [(\"?\" * len(target), [])]
        # while q:
        #     cur_str, seq = q.pop(0)
        #     for i in range(0, n-k+1):
        #         new_str = cur_str[:i] + stamp + cur_str[i + k:]
        #         if new_str == target:
        #             return seq + [i]
        #         if new_str not in visited:
        #             visited.add(new_str)
        #             q.append((new_str, seq + [i]))
        # return []
    
    
        #
        # DFS & DP ----- 96 ms (94.35%) / 20.6 MB (6.00%)
        # 
        # Here are few rules for this problem:
        #
        # 1. stamp[0] has to be equal with target[0]
        # 2. stamp[-1] has to be equal with target[-1]
        # 3. We keep checking pairs of (stamp[s], target[t]). When checking (s, t). 
        #    If stamp[s] equals to target[t], we can move forward to (s+1, t+1). 
        #    Otherwise, we add a new stamp at index t+1 and stamp[0] has to be equal with target[t+1]. 
        #    Then we move forward to (0, t+1). (If stamp[0] != target[t+1] here, 
        #    there is no way to stamp without overwriting previous stamped sequence).
        # 4. When a stamp is used up, s == len(stamp), and we can try any i that stamp[i] == target[t]. 
        #    In such case, we stamp at index t-i at the beginning of the sequence so that 
        #    stamp[:i] will be overwritten by \"later\" stamps and we move forward to (i, t).
        # 5. We finish our search when we reach the end of target or t == len(target). 
        #    Based on rule #2, if i == len(stamp) as well, we have a valid sequence.
        # 
        # Based on these rules, we can build a DFS with memoization. The speed beats 90%.
        # -----------------------------------------------------------------------------------------------
        memo, ls, lt = {}, len(stamp), len(target)
        
        def dfs(s, t, seqs):
            if t == lt:
                memo[s, t] = seqs if s == ls else []
            if (s, t) not in memo:
                if s == ls:
                    for i in range(ls):
                        if stamp[i] != target[t]:
                            continue
                        cand = dfs(i, t, [t-i]+seqs)
                        if cand:
                            memo[s, t] = cand
                            break
                        else: 
                            memo[s, t] = []
                elif target[t] == stamp[s]:
                    cand = dfs(s+1, t+1, seqs)
                    memo[s, t] = cand if cand else dfs(0, t+1, seqs+[t+1])
                else:
                    memo[s, t] = []
            return memo[s, t]
        
        return dfs(0, 0, [0])
                
            
\"\"\"
Test Cases
movesToStamp(\"abc\", \"ababc\")
movesToStamp(\"ab\", \"babab\")
movesToStamp(\"o\", \"oooooooooooooooooooo\")

\"\"\"

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        stamp_len, target_len, stamp, target, result = len(stamp), len(target), list(stamp), list(target), []
        changed = True
        while changed:
            changed = False
            for i in range(target_len - stamp_len + 1):
                changed |= self.check(stamp, target, i, result)
        return result[::-1] if target == ['?'] * target_len else []   
    
    def check(self, stamp, target, i, result):
        changed = False
        for j in range(len(stamp)):
            if target[i+j] == '?': continue
            if stamp[j] != target[i+j]: return False
            changed = True
        if changed:
            target[i:i+len(stamp)] = ['?'] * len(stamp)
            result.append(i)
        return changed

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        ret = []
        stamp = list(stamp)
        target= list(target)
        cnt = 0
        candidates = [i for i in range(len(target)-len(stamp)+1)]
        # print(candidates)
        while cnt < len(target) and len(candidates) > 0:
            nxt = set()
            for i in candidates:
                l = min(len(stamp), len(target)-i)
                if (all(target[i+j] in ['*', stamp[j]] for j in range(l)) 
                    and any(target[i+j] != '*' for j in range(l))):
                    nxt |= set(max(0, i-j) for j in range(l))
                    for j in range(i, i+l):
                        if target[j] != '*':
                            cnt +=1
                        target[j] = '*'
                    ret.append(i)
            candidates = nxt
            # print(target)
            
        return ret[::-1] if cnt == len(target) else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        locks = collections.defaultdict(set)
        count_locks = collections.defaultdict(int)
        
        last_window = len(target)-len(stamp)
        
        for i in range(last_window+1):
            for j in range(i, i+len(stamp)):
                if stamp[j-i] != target[j]:
                    locks[j].add(i)
                    count_locks[i] += 1
            
        available_windows = collections.deque([])
        for i in range(last_window+1):
            if count_locks[i] == 0:
                available_windows.append(i)
                
        res = []
        target = list(target)
        while available_windows:
            window = available_windows.popleft()
            res.append(window)
            for i in range(window, window+len(stamp)):
                if target[i] == \"?\":
                    pass
                else:
                    target[i] = \"?\"
                    while locks[i]:
                        w = locks[i].pop()
                        count_locks[w] -= 1
                        if count_locks[w] == 0:
                            available_windows.append(w)
        if any(c != \"?\" for c in target):
            return []
        return res[::-1]
                        

# ababcbc
class Solution:
    def movesToStamp(self, s, t):
        n, m, t, s, res = len(t), len(s), list(t), list(s), []

        def check(i):
            changed = False
            for j in range(m):
                if t[i + j] == '?': continue
                if t[i + j] != s[j]: return False
                changed = True
            if changed:
                t[i:i + m] = ['?'] * m
                res.append(i)
            return changed

        changed = True
        while changed:
            changed = False
            for i in range(n - m + 1):
                changed |= check(i)
        return res[::-1] if t == ['?'] * n else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        def helper(idx):
            num = len(stamp)
            for i in range(len(stamp)):
                if target[i+idx] == '*':
                    num -= 1
                elif target[i+idx] != stamp[i]:
                    return 0
            target[idx:idx+len(stamp)] = ['*']*len(stamp)
            return num
        
        seen = [0]*len(target)
        total = 0
        res = []
        target = list(target)
        while total < len(target):
            found = False
            for i in range(len(target)-len(stamp)+1):
                if seen[i] == 1: continue
                num = helper(i)
                if num == 0: continue
                seen[i] = 1
                total += num
                found = True
                res.append(i)
            if not found: return []
        return res[::-1]


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m=len(stamp)
        n=len(target)
        stamp=list(stamp)
        target=list(target)
        noleft=n
        c=[]
        while(noleft>0):
            onc=False
            for i in range(n-m+1):
                oc=False
                no=0
                for j in range(i,i+m):
                    if(target[j]==stamp[j-i]):
                        no+=1
                    elif(target[j]==\"?\"):
                        continue
                    else:
                        oc=True
                        break
                if(oc==False)and(no!=0):
                    onc=True
                    c.append(i)
                    noleft-=no
                    for j in range(i,i+m):
                        target[j]=\"?\"
            if(onc==False):
                return []
        c.reverse()
        return c
                
                
                        
        

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        res = []
        all_len = 0
        cur_len = 1
        while cur_len:
            cur_len = 0
            for i in range(len(stamp)):
                for j in range(len(stamp) - i):
                    cur_stamp = '*' * i + stamp[i: len(stamp) - j] + '*' * j
                    # print(cur_stamp)
                    idx = target.find(cur_stamp)
                    while idx != -1:
                        target = target[:idx] + '*' * len(cur_stamp) + target[idx + len(cur_stamp):]
                        # print(cur_stamp, target)
                        res.append(idx)
                        cur_len += len(stamp) - i - j
                        idx = target.find(cur_stamp)
            all_len += cur_len
        
        #print(all_len)
        return res[::-1] if all_len == len(target) else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # abc??
        # ?abc?
        # ??abc
        
        def num_match(stamp, target):
            ret = 0
            for (c1, c2) in zip(stamp, target):
                if c1 == c2:
                    ret += 1
                elif c2 != '?':
                    return -1
            return ret

        remain = len(target)
        ret= []
        cur = list(target)
        while remain > 0:
            tmp = remain
            match = 0
            for l in range(len(target)):
                r = l + len(stamp) - 1
                if r >= len(target):
                    break
                match = num_match(stamp, cur[l:r + 1])
                if match > 0:
                    cur[l:l + len(stamp)] = ['?'] * len(stamp)
                    ret.append(l)
                    remain -= match
                    
            if tmp == remain:
                return []
        
        return ret[::-1]


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        memo, ls, lt = {}, len(stamp), len(target)
        def dfs(s, t, seqs):
            if t == lt:
                memo[s, t] = seqs if s == ls else []
            if (s, t) not in memo:
                if s == ls:
                    for i in range(ls):
                        cand = dfs(i, t, [t-i]+seqs)
                        if cand:
                            memo[s, t] = cand
                            break
                    else: 
                        memo[s, t] = []
                elif target[t] == stamp[s]:
                    cand = dfs(s+1, t+1, seqs)
                    memo[s, t] = cand if cand else dfs(0, t+1, seqs+[t+1])
                else:
                    memo[s, t] = []
            return memo[s, t]
            
        return dfs(0, 0, [0])

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # greedy
        res = []
        seq = list(target)
        m, n = len(stamp), len(target)
        def check(i):
            changed = False
            full = True
            for j in range(m):
                if seq[i+j]=='?': 
                    continue                    
                else:
                    if target[i+j] == stamp[j]:
                        changed = True
                    else:
                        full = False
            if changed and full:
                seq[i:i+m] = ['?'] * m
                return True
            return False
        
        changed = True
        while changed:
            changed = False
            for i in range(n-m+1):
                if check(i):
                    res.append(i)
                    changed = True
        return res[::-1] if all([c=='?' for c in seq]) else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        stampList = list(stamp)
        targetList = list(target)
        
        result = []
        changed = True
        while changed:
            changed = False
            for i in range(len(targetList) - len(stampList) + 1):
                temp = self.validTarget(stampList, targetList, i)
                
                if temp:
                    changed = True
                    result += [i]
            
            if not changed:
                break
        
        if targetList == [\"?\"] * len(targetList):
            return reversed(result)
        else:
            return []
        
        
    def validTarget(self, stamp, target, i):
        
        changed = False
        
        for j in range(len(stamp)):
            
            if target[j+i] == \"?\":
                continue
            if stamp[j] != target[i+j]:
                return False
            
            changed = True
        
        if not changed:
            return False
        
        for j in range(len(stamp)):
            target[j+i] = \"?\"
        
        return True

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        ret = []
        stamp = list(stamp)
        target= list(target)
        cnt = 0
        candidates = [i for i in range(len(target)-len(stamp)+1)]
        # print(candidates)
        while cnt < len(target) and len(candidates) > 0:
            nxt = []
            for i in candidates:
                l = min(len(stamp), len(target)-i)
                if (all(target[i+j] in ['*', stamp[j]] for j in range(l)) 
                    and any(target[i+j] != '*' for j in range(l))):
                    nxt += [max(0, i-j) for j in range(l)]
                    for j in range(i, i+l):
                        if target[j] != '*':
                            cnt +=1
                        target[j] = '*'
                    ret.append(i)
            candidates = nxt
            # print(target)
            
        return ret[::-1] if cnt == len(target) else []


def getstamps(s):
    stamps = []
    for i in range(0, len(s)):
        for j in range(len(s), -1, -1):
            if i + len(s)-j <len(s):
                stamp = '*'*i+s[i:j]+'*'*(len(s)-j)
                stamps.append(stamp)
    return stamps

def stampseq(s, t):
    stamps = getstamps(s)
    print(stamps)
    flag = True
    result = []
    while flag:
        flag = False
        for stamp in stamps:
            pos = t.find(stamp)
            while(pos != -1):
                result.append(pos)
                t = t[:pos] + '*'*len(s) + t[pos+len(s):]
                flag = True
                pos = t.find(stamp)
            if t == '*'*len(t):
                return reversed(result)
    return []
        
        
class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        return stampseq(stamp, target)

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        s_l, t_l = len(stamp), len(target)
        t = list(target)
        res = list()
        
        def stmp(i):
            # match the whole stamp
            match = False
            for j in range(s_l):
                if t[i + j] == '?':
                    continue
                elif t[i + j] != stamp[j]:
                    return False
                match = True
            if match:
                t[i : i + s_l] = ['?'] * s_l
                res.append(i)
            return match
        
        match = True
        # loop until no more match
        while match:
            match = False
            for i in range(t_l - s_l + 1):
                match |= stmp(i)
        
        return res[::-1] if t == ['?'] * t_l else list()
            


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        tl,sl = len(target),len(stamp)
        t,s = list(target),list(stamp)
        res = []
        def check(i):
            signal = False
            for j in range(sl):
                if t[i+j] == '?':continue
                if t[i+j] != s[j]:return False
                signal = True
            if signal:
                t[i:i+sl] = ['?']*sl
                res.append(i)
            return signal
        signal = True
        while signal:
            signal = False
            for i in range(tl-sl+1):
                signal = signal | check(i)
        return res[::-1] if t == ['?']*tl else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        from collections import deque, defaultdict
        
        ls = len(stamp)
        lt = len(target)
        
        flag = [False] * lt
        todo_mp = defaultdict(set)
        wait_mp = defaultdict(set)
        
        for i in range(lt - ls + 1):
            for j in range(ls):
                if stamp[j] == target[i + j]:
                    todo_mp[i].add(i + j)
                else:
                    wait_mp[i].add(i + j)
        
        q = deque([i for i in range(lt - ls + 1) if len(wait_mp[i]) == 0])
        
        ret = []
        visited = set(q)
        while len(q) > 0 and all(flag) is False:
            idx = q.popleft()
            to_add = False
            for item in todo_mp[idx]:
                if flag[item] is False:
                    flag[item] = True
                    to_add = True
            if to_add is True:
                ret.append(idx)
                
            for nei in range(max(idx - ls + 1, 0), min(idx + ls - 1, lt - ls) + 1):
                if nei in visited:
                    continue
                for t in todo_mp[idx]:
                    wait_mp[nei].discard(t)
                if len(wait_mp[nei]) == 0:
                    q.append(nei)
                    visited.add(nei)
        
        if all(flag) is True:
            return ret[::-1]
        return []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        n, m, t, s, res = len(target), len(stamp), list(target), list(stamp), []
        
        def check(i):
            changed = False
            for j in range(m):
                if t[i+j] == '?': continue
                if t[i+j] != s[j]: return False
                changed = True
                
            if changed:
                t[i:i+m] = ['?'] * m
                res.append(i)
            return changed
        
        changed = True
        while changed:
            changed = False
            for i in range(n-m+1):
                changed |= check(i)
        return res[::-1] if t ==['?'] * n else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        def okay(s):
            ret = False
            for c1,c2 in zip(stamp,s):
                if c2 == '?':continue
                elif c1 != c2:return False
                else:
                    ret = True
            return ret
        
        todo = len(target)-len(stamp)+1
        res = []
        idx = 0
        while idx<todo:
            prv = idx
            for i in range(todo):
                if okay(target[i:i+len(stamp)]):
                    idx += 1
                    res.append(i)
                    target = target[:i]+'?'*(len(stamp))+target[i+len(stamp):]
            if target == '?'*len(target):
                return res[::-1]
            if idx == prv:break
        return []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        if stamp not in target:
            return []
        
        m, n = len(stamp), len(target)
        cnt = 0
        res = []
        
        while cnt < 10:
            flag = False
            for i in range(n-m+1):
                if target[i:i+m] != \".\"*m and self.helper(stamp, target[i:i+m]):
                    flag = True
                    target = target[:i] + \".\"*m + target[i+m:]
                    res.append(i)
                    
            if target == \".\"*n:
                return res[::-1]
            if not flag:
                return []
        cnt += 1
            
        return []
    
    def helper(self, stamp, target):
        for i in range(len(stamp)):
            if target[i] != \".\" and stamp[i] != target[i]:
                return False
        return True

class Solution:
    # O(mnn) time, O(n) space
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        target_list = list(target)
        result = []
        
        def is_changed(i):
            changed = False
            for j in range(m):
                if target_list[i + j] == \"?\":
                    continue
                if target_list[i + j] != stamp[j]:
                    return False
                # equal to stamp[j] and should be changed to ?
                changed = True
            if changed:
                for j in range(m):
                    target_list[i + j] = \"?\"
                result.append(i)
            return changed
        
        changed = True
        while changed:
            changed = False
            for i in range(n - m + 1):
                changed |= is_changed(i)
        
        if all(x == \"?\" for x in target_list):
            return result[::-1]
        return []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        root = '?' * (n := len(target))
        res = []
        moves = 0
        def match(s, t):
            # return all(ch1 in {ch2, '?'} for ch1, ch2 in zip(s, t))
            for ch1, ch2 in zip(s, t):
                if ch1 == '?':
                    continue
                elif ch1 != ch2:
                    return False
            return True
        
        while moves <= 10 * n:
            pre_move = 0
            for i in range(n - (m := len(stamp)) + 1):
                if target[i] in {stamp[0], '?'} and match(target[i:i+m], stamp):
                    moves += 1
                    res.append(i)
                    target = target[:i] + '?' * m + target[i+m:]
                    
                    if target == root:
                        return reversed(res)
            if pre_move == moves:
                return []
        return []    


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        root = '?' * (n := len(target))
        res = []
        moves = 0
        def match(s, t):
            for c1, c2 in zip(s, t):
                if c1 == '?':
                    continue
                elif c1 != c2:
                    return False
            return True
        
        while moves <= 10 * n:
            prev_move = moves
            for i in range(n - (m := len(stamp)) + 1):
                if target[i] in {stamp[0], '?'} and match(target[i:i+m], stamp):
                    moves += 1
                    res.append(i)
                    target = target[:i] + '?' * m + target[i+m:]
                    
                    if target == root:
                        return res[::-1]
            if prev_move == moves:
                return []
        return []
           


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        root = '?' * (n := len(target))
        res = []
        moves = 0
        def match(s, t):
            for ch1, ch2 in zip(s, t):
                if ch1 == '?':
                    continue
                elif ch1 != ch2:
                    return False
            return True
        while moves <= 10 * n:
            pre_move = 0
            for i in range(n - (m := len(stamp)) + 1):
                if target[i] in {stamp[0], '?'} and match(target[i:i+m], stamp):
                    moves += 1
                    res.append(i)
                    target = target[:i] + '?' * m + target[i+m:]
                    
                    if target == root:
                        return reversed(res)
            if pre_move == moves:
                return []
        return []    


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        res = []
        ns,nt = len(stamp),len(target)
        final = \"?\"*nt
        def same(ind):
            other = False
            for i in range(ns):
                if target[i+ind] not in stamp[i]+\"?\":
                    return False
                if target[i+ind]!=\"?\":
                    other = True
            return other
        change = True
        while change:
            change = False
            for ind in range(nt-ns+1):
                if same(ind):
                    change=True
                    res.append(ind)
                    target=target[:ind]+\"?\"*ns+target[ind+ns:]
        return res[::-1] if all(i==\"?\" for i in target) else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        N , M = len(target), len(stamp)
        def cor(s):
            result = False
            for c1, c2 in zip(s,stamp):
                if c1 == '?':
                    continue
                elif c1 != c2:
                    return False
                else:
                    result = True
            return result
        base, times, max_times, indexes = '?' * N , 0 , 10* N, []                
        while times < max_times:
            start = times
            for i in range(N - M + 1):                
                if cor(target[i:i + M  ]):
                    times += 1
                    indexes.append(i)
                    target = target[:i] + '?' *  M + target[i+M:]                
            if target == base:
                return indexes[::-1]
                
            if times == start:
                break
        print(\"here\")
        return  []
            
                
                
            
            
            

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        if set(stamp) < set(target) or len(stamp) > len(target):
            return []
        
        patterns = set()
        for l in range(1, len(stamp) + 1):
            for i in range(len(stamp) - l + 1):
                patterns.add('*' * i + stamp[i:i + l] + '*' * (len(stamp) - i - l))
            
        goal = '*' * len(target)
        def dfs(cur, path, moves):
            if cur == goal:
                return path
            
            if not moves:
                return []
            
            old_moves = moves
            for pattern in patterns:
                i = cur.find(pattern)
                if i >= 0:
                    cur = cur[:i] + '*' * len(stamp) + cur[i + len(stamp):]
                    path.append(i)
                    moves -= 1
            
            if old_moves == moves:
                return []
            
            return dfs(cur, path, moves)
        
        return dfs(target, [], 10 * len(target))[::-1]


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        lens,lent = len(stamp), len(target)
        out = []
        q = collections.deque()
        done = set()
        # create v,t 
        v = [set() for _ in range(lent-lens+1)]
        t = [set() for _ in range(lent-lens+1)]
        # iterate over all offsets
        for i in range(len(target)-len(stamp)+1):
            for j in range(len(stamp)):
                if stamp[j] == target[i+j]:
                    v[i].add(i+j)
                else:
                    t[i].add(i+j)
            if len(t[i]) == 0:
                out.append(i)
                for j in range(len(stamp)):
                    done.add(i+j)
                q.append(i)
        while q:
            offset = q.popleft()
            for of in range(max(0,offset-lens+1),min(lent-lens+1,offset+lens)): 
                t[of] -= done
                if len(t[of]) == 0:
                    if len(v[of] - done) > 0:
                        q.append(of)
                        done |= v[of]
                        out.append(of)
        if len(done) == lent:             
            return out[::-1]
        return []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        def check_equal(sub_string):
            
            for c1, c2 in zip(list(sub_string), list(stamp)):
                if c1 != \"?\" and c1 != c2:
                    return False
            return True
                
        stamp_length = len(stamp)
        end_result = \"?\" * len(target)
        no_check_string = \"?\" * stamp_length

        res = []
        for _ in range(10 * len(target)):
            found = False
            for ti in range(len(target) - stamp_length + 1):
                sub_string = target[ti:ti+stamp_length]
                # print(sub_string)
                if sub_string == no_check_string:
                    continue
                if check_equal(sub_string):
                    target = target[:ti] + no_check_string + target[ti + stamp_length:]
                    found = True
                    res += [ti]
                    break
            
            if found:
                if target == end_result:
                    return res[::-1]
            
            else:
                return []
            
        return []
                
            
            
            
            
            
        

'''
\"aabcaca\"
 0123456
  x
 
matched = [set() for _ in range(M-N)]

que = [1]
for window_start in range(i - n + 1, i + n):
    for j in range(i, i+n):
        todo[window_start].discard(j)
        if canMatch(todo[window_start]):
            que.append(window_start)
'''
class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        '''greedy. everytime put the totally matched window to the que
            then update the windows that are affected
            then if updated window is totally matched, append to que.
            keep doing it.
        '''

        M = len(stamp)
        N = len(target)
        nwin = N - M + 1
        matched = [set() for _ in range(nwin)]
        done = set()
        
        for win_start in range(nwin):
            for i, (c1, c2) in enumerate(zip(target[win_start: win_start+M], stamp)):
                if c1 == c2: matched[win_start].add(i + win_start)
        
        res = []
        que = deque()
        for win_start in range(nwin):
            if len(matched[win_start]) == M:
                que.append(win_start)
                res.append(win_start)
                done.add(win_start)
        
        #print(que, matched) 
        
        while que:
            win_start = que.popleft() #done window
            #new windows that are affected
            
            for nws in range(max(0, win_start-M +1), min(nwin, win_start + M)):
                #add the pos if not matched in new window yet
                if nws in done: continue
                for pos in range(win_start, win_start + M): # pos in done
                    if nws <= pos < nws + M:
                        matched[nws].add(pos)
                        
                if len(matched[nws]) == M:
                    que.append(nws)
                    done.add(nws)
                    res.append(nws)
            
        return res[::-1] if all([d in done for d in range(nwin)]) else []
                    
                
            
            
            
            


class Solution:
    def movesToStamp(self, stamp, target):
        memo, ls, lt = {}, len(stamp), len(target)
        def dfs(s, t, seqs):
            if t == lt:
                memo[s, t] = seqs if s == ls else []
            if (s, t) not in memo:
                if s == ls:
                    for i in range(ls):
                        cand = dfs(i, t, [t-i]+seqs)
                        if cand:
                            memo[s, t] = cand
                            break
                    else: 
                        memo[s, t] = []
                elif target[t] == stamp[s]:
                    cand = dfs(s+1, t+1, seqs)
                    memo[s, t] = cand if cand else dfs(0, t+1, seqs+[t+1])
                else:
                    memo[s, t] = []
            return memo[s, t]
        return dfs(0, 0, [0])


class Solution:
    def movesToStamp(self, stamp, target):
        ns = len(stamp)        
        stamp_patterns = []
\t\t# Step - 1:
        # we need to collect all possible stamp patters, like
        # 'abcde'
        # 'abcd*'
        # '*bcde'
        # 'abc**'
        # '**cde'
        # 'ab***'
        # '*bc**'
        # '**cd*'
        # '***de'
        # ‘****e’ and etc
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
\t\t# Step - 2
        # '*****' is our final target
        while target != '*' * nt:
            old_target = target
            # greedy, keep replace current target string with possible patter
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return res[::-1]
        

class Solution:
    def movesToStamp(self, stamp, target):
        ns = len(stamp)        
        stamp_patterns = []
\t\t
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
        while target != '*' * nt:
            old_target = target
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return res[::-1]

class Solution:
    def movesToStamp(self, stamp, target):
        ns = len(stamp)        
        stamp_patterns = []
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
        while target != '*' * nt:
            old_target = target
            # greedy, keep replace current target string with possible patter
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return res[::-1]

class Solution:
    def movesToStamp(self, stamp, target):
        ns = len(stamp)        
        stamp_patterns = []
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
        while target != '*' * nt:
            old_target = target
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return res[::-1]

class Solution:
    def movesToStamp(self, stamp, target):
        ns = len(stamp)        
        stamp_patterns = []
\t\t# Step - 1:
        # we need to collect all possible stamp patters, like
        # 'abcde'
        # 'abcd*'
        # '*bcde'
        # 'abc**'
        # '**cde'
        # 'ab***'
        # '*bc**'
        # '**cd*'
        # '***de'
        # ‘****e’ and etc
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
\t\t# Step - 2
        # '*****' is our final target
        while target != '*' * nt:
            old_target = target
            # greedy, keep replace current target string with possible patter
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return res[::-1]


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        if not stamp or not target:
            return []
        m, n = len(stamp), len(target)
        if m > n:
            return []
        if m == n:
            if stamp == target:
                return [0]
            else:
                return []
        if '?' in target:
            return []

        invalid = []
        invert_idx = [set() for _ in range(n)]

        for i in range(n - m + 1):
            mismatch = set()
            for j in range(m):
                if target[i + j] != '?' and target[i + j] != stamp[j]:
                    mismatch.add(i + j)
                    invert_idx[i + j].add(i)
            invalid.append(mismatch)

        cleared = set()
        seq = []
        visited = set()

        while len(cleared) < n:
            not_found = True
            for i in range(len(invalid)):
                if i not in visited and not invalid[i]:
                    not_found = False
                    seq.append(i)
                    visited.add(i)

                    for j in range(m):
                        cleared.add(i+j)
                        if invert_idx[i + j]:
                            for k in invert_idx[i + j]:
                                invalid[k].remove(i + j)
                            invert_idx[i + j].clear()
                    break
            if not_found:
                return []
        return seq[::-1]

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        root = '?' * (n := len(target))
        res = []
        moves = 0
        def match(s, t):
            return all(ch1 in {ch2, '?'} for ch1, ch2 in zip(s, t))
            # for ch1, ch2 in zip(s, t):
            #     if ch1 == '?':
            #         continue
            #     elif ch1 != ch2:
            #         return False
            # return True
        
        while moves <= 10 * n:
            pre_move = 0
            for i in range(n - (m := len(stamp)) + 1):
                if target[i] in {stamp[0], '?'} and match(target[i:i+m], stamp):
                    moves += 1
                    res.append(i)
                    target = target[:i] + '?' * m + target[i+m:]
                    
                    if target == root:
                        return reversed(res)
            if pre_move == moves:
                return []
        return []    


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        root = '?' * (n := len(target))
        res = []
        moves = 0
        def match(s, t):
            return all(ch1 in {ch2, '?'} for ch1, ch2 in zip(s, t))
            # for ch1, ch2 in zip(s, t):
            #     if ch1 == '?':
            #         continue
            #     elif ch1 != ch2:
            #         return False
            # return True
        
        while moves <= 10 * n:
            pre_move = 0
            for i in range(n - (m := len(stamp)) + 1):
                if target[i] in {stamp[0], '?'} and all(ch1 in {ch2, '?'} for ch1, ch2 in zip(target[i:i+m], stamp)):
                    moves += 1
                    res.append(i)
                    target = target[:i] + '?' * m + target[i+m:]
                    
                    if target == root:
                        return reversed(res)
            if pre_move == moves:
                return []
        return []    


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        ns = len(stamp)        
        stamp_patterns = []
\t\t# Step - 1:
        # we need to collect all possible stamp patters, like
        # 'abcde'
        # 'abcd*'
        # '*bcde'
        # 'abc**'
        # '**cde'
        # 'ab***'
        # '*bc**'
        # '**cd*'
        # '***de'
        # ‘****e’ and etc
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
\t\t# Step - 2
        # '*****' is our final target
        while target != '*' * nt:
            old_target = target
            # greedy, keep replace current target string with possible patter
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return res[::-1]
        

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        memo, ls, lt = {}, len(stamp), len(target)
        def dfs(s, t, seqs):
            if t == lt:
                memo[s, t] = seqs if s == ls else []
            if (s, t) not in memo:
                # stamp down
                if s == ls:
                    for i in range(ls):
                        cand = dfs(i, t, [t-i]+seqs)
                        if cand:
                            memo[s, t] = cand
                            break
                    else: 
                        memo[s, t] = []
                # stamp up
                elif target[t] == stamp[s]:
                    cand = dfs(s+1, t+1, seqs)
                    memo[s, t] = cand if cand else dfs(0, t+1, seqs+[t+1])
                # no match
                else:
                    memo[s, t] = []
            return memo[s, t]
            
        return dfs(0, 0, [0])

class Solution:
    def movesToStamp(self, stamp, target):
        ns = len(stamp)        
        stamp_patterns = []
        # we need to collect all possible stamp patters, like
        # 'abcde'
        # 'abcd*'
        # '*bcde'
        # 'abc**'
        # '**cde'
        # 'ab***'
        # '*bc**'
        # '**cd*'
        # '***de'
        # ‘****e’ and etc
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
        # '*****' is our final target
        while target != '*' * nt:
            old_target = target
            # greedy, keep replace current target string with possible patter
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        assert len(res) <= 10 * len(target)
        return res[::-1]

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        n = len(target)
        m = len(stamp)
        totalStamped = 0
        turnStamped = -1
        res = []

        while True:
            turnStamped = 0

            for coverSize in range(m, 0, -1): # size: the window size that will stamp over, so *bc , size = 2, abc , size = 3
                for i in range(m-coverSize+1): # i: the startIdx of \"*\" from left, if left = 0 , then based on m-coverSize, we can figure out rightIdx to add \"*\"
                    newStamp = \"*\"*i + stamp[i:i+coverSize] + \"*\"*(m-coverSize-i)
                    pos = target.find(newStamp)

                    while pos != -1:
                        res.append(pos)
                        turnStamped += coverSize # \"abc\" will cover 3 while \"ab*\" only cover 2
                        target = target[:pos] + \"*\"*len(stamp) + target[pos+len(newStamp):]
                        pos = target.find(newStamp)

            totalStamped += turnStamped
            if turnStamped == 0:
                break

        return res[::-1] if totalStamped == len(target) else []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        S = list(stamp)
        T = list(target)
        visited = [False for _ in range(len(T))]
        ans = []
        cnt = 0
        while cnt < len(T):
            found = False
            for i in range(len(T) - len(S) + 1):
                if not visited[i] and self.canStamp(S, T, i):
                    cnt += self.doStamp(S, T, i)
                    found = True
                    ans.append(i)
                    visited[i] = True
                    break
            if not found:
                return []
        return ans[::-1]
    
    
    def canStamp(self, S, T, start):
        for i in range(len(S)):
            if S[i] != T[i+start] and T[i+start] != \"?\":
                return False
        return True
    
    def doStamp(self, S, T, start):
        cnt = 0
        for i in range(len(S)):
            if T[i + start] != \"?\":
                cnt += 1
                T[i + start] = \"?\"
        return cnt

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        S = list(stamp)
        T = list(target)
        visited = [False for _ in range(len(T))]
        ans = []
        cnt = 0
        while cnt < len(T):
            found = False
            for i in range(len(T) - len(S) + 1):
                if not visited[i] and self.canStamp(S, T, i):
                    cnt += self.doStamp(S, T, i)
                    ans.append(i)
                    visited[i] = True
                    found = True
                    break
            if not found:
                return []
        return ans[::-1]
        
    def canStamp(self, S, T, start) -> bool:
        for i in range(len(S)):
            if S[i] != T[start+i] and T[start+i] != \"?\":
                return False
        return True
    
    def doStamp(self, S, T, start) -> int:
        cnt = 0
        for i in range(len(S)):
            if T[start+i] != \"?\":
                T[start+i] = \"?\"
                cnt += 1
        return cnt

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        if stamp not in target:
            return []

        m, n = len(stamp), len(target)
        cnt = 0
        res = []

        while cnt < 1000:

            for i in range(n-m+1):

                # check any partial overlap of a stamp with target
                if target[i:i+m] != \".\"*m and self.find(stamp, target[i:i+m]):
                    target = target[:i] + \".\"*m + target[i+m:]
                    res.append(i)
                    break
            else:
                return []
 
            if target == \".\" * n:
                return res[::-1]
            cnt += 1

        return []

    def find(self, stamp, target):
        for i in range(len(stamp)):
            if target[i] != \".\" and stamp[i] != target[i]:
                return False
        return True        

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        done = set()
        n = len(stamp)
        m = len(target)
        candidates = { i for i in range(m-n+1) }
        res = []
        
        def check(i):
            j = 0
            count = 0
            while j < n :
                if i in done:
                    j += 1
                    i += 1
                elif stamp[j] == target[i]:
                    count += 1
                    i += 1
                    j += 1
                else:
                    return False
            return count > 0
        
        while len(done) < m :
            found = 0
            for i in candidates:
                if check(i):
                    for j in range(i,i+n):
                        done.add(j)
                    res.append(i)
                    found = 1
                    break
            if not found:
                return []
            else:
                candidates.remove(i)
                
                    
        return res[::-1]
                
            
        
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        if set(stamp) != set(target):
            return []
        done = set()
        n = len(stamp)
        m = len(target)
        candidates = { i for i in range(m-n+1) }
        res = []
        
        def check(i):
            j = 0
            count = 0
            while j < n :
                if i in done:
                    j += 1
                    i += 1
                elif stamp[j] == target[i]:
                    count += 1
                    i += 1
                    j += 1
                else:
                    return False
            return count > 0
        
        while len(done) < m :
            found = 0
            for i in candidates:
                if check(i):
                    for j in range(i,i+n):
                        done.add(j)
                    res.append(i)
                    found = 1
                    break
            if not found:
                return []
            else:
                candidates.remove(i)
                
                    
        return res[::-1]
                
            
        
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        ns = len(stamp)        
        stamp_patterns = []
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.reverse()        

        res = []
        nt = len(target)

        while target != '*' * nt:
            old_target = target
            # greedy, keep replace current target string with possible pattern
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return reversed(res)

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        memo, ls, lt = {}, len(stamp), len(target)
        def dfs(s, t, seqs):
            if t == lt:
                memo[s, t] = seqs if s == ls else []
            if (s, t) not in memo:
                if s == ls:
                    for i in range(ls):
                        cand = dfs(i, t, [t-i]+seqs)
                        if cand:
                            memo[s, t] = cand
                            break
                    else: 
                        memo[s, t] = []
                elif target[t] == stamp[s]:
                    cand = dfs(s+1, t+1, seqs)
                    memo[s, t] = cand if cand else dfs(0, t+1, seqs+[t+1])
                else:
                    memo[s, t] = []
            return memo[s, t]
        return dfs(0, 0, [0])

class Solution:
    def movesToStamp(self, stamp, target):
        ns = len(stamp)        
        stamp_patterns = []
        # we need to collect all possible stamp patters, like
        # 'abcde'
        # 'abcd*'
        # '*bcde'
        # 'abc**'
        # '**cde'
        # 'ab***'
        # '*bc**'
        # '**cd*'
        # '***de'
        # ‘****e’ and etc
        for window_size in range(1, ns + 1):
            for i in range(ns - window_size + 1):
                curr = '*' * i + stamp[i:i + window_size] + '*' * (ns - window_size - i)
                stamp_patterns.append(curr)
        stamp_patterns.append('*' * ns)

        res = []
        nt = len(target)
        # '*****' is our final target
        while target != '*' * nt:
            old_target = target
            # greedy, keep replace current target string with possible patter
            for pattern in stamp_patterns:
                inx = target.find(pattern)
                if inx != -1:
                    target = target[:inx] + '*' * ns + target[inx + ns:]
                    res.append(inx)
            if old_target == target:
                return []
        
        return res[::-1]

class Solution:
    def movesToStamp(self, s: str, t: str) -> List[int]:
        if s[0] != t[0] or s[-1] != t[-1]: return []
        n, m = len(s), len(t)
        path = [0] * m
        pos = collections.defaultdict(set)
        for i, c in enumerate(s): pos[c].add(i)

        def dfs(i, index):
            path[i] = index
            if i == m - 1: return index == n - 1
            nxt_index = set()
            if index == n - 1:  # rule 2
                nxt_index |= pos[t[i + 1]]
            elif s[index + 1] == t[i + 1]:  # rule 0
                nxt_index.add(index + 1)
            if s[0] == t[i + 1]:  # rule 1
                nxt_index.add(0)
            return any(dfs(i + 1, j) for j in nxt_index)

        def path2res(path):
            down, up = [], []
            for i in range(len(path)):
                if path[i] == 0:
                    up.append(i)
                elif i and path[i] - 1 != path[i - 1]:
                    down.append(i - path[i])
            return down[::-1] + up

        if not dfs(0, 0): return []
        print(path)
        return path2res(path)


class Solution:
    def movesToStamp(self, s, t):
        if s[0] != t[0] or s[-1] != t[-1]: return []
        n, m = len(s), len(t)
        path = [0] * m
        pos = collections.defaultdict(set)
        for i, c in enumerate(s): pos[c].add(i)

        def dfs(i, index):
            path[i] = index
            if i == m - 1: return index == n - 1
            nxt_index = set()
            if index == n - 1:  # rule 2
                nxt_index |= pos[t[i + 1]]
            elif s[index + 1] == t[i + 1]:  # rule 0
                nxt_index.add(index + 1)
            if s[0] == t[i + 1]:  # rule 1
                nxt_index.add(0)
            return any(dfs(i + 1, j) for j in nxt_index)

        def path2res(path):
            down, up = [], []
            for i in range(len(path)):
                if path[i] == 0:
                    up.append(i)
                elif i and path[i] - 1 != path[i - 1]:
                    down.append(i - path[i])
            return down[::-1] + up

        if not dfs(0, 0): return []
        return path2res(path)        

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        stamp = list(stamp)
        target = list(target)
        result = []
        
        def change(i):
            if target[i:i + m].count('?') == m:
                return False
            ch = False
            for j in range(m):
                if target[i + j] == '?':
                    continue
                if target[i + j] != stamp[j]:
                    ch = False
                    break
                ch = True
            if ch:
                target[i:i + m] = ['?'] * m
                result.append(i)
            return ch
        while True:
            if not any(change(i) for i in range(n - m + 1)):
                break
        return reversed(result) if target.count('?') == n else []

class Solution:
    def movesToStamp(self, s: str, t: str) -> List[int]:
        if s[0] != t[0] or s[-1] != t[-1]: return []
        n, m = len(s), len(t)
        path = [0] * m
        pos = collections.defaultdict(set)
        for i, c in enumerate(s): pos[c].add(i)

        def dfs(i, index):
            path[i] = index
            if i == m - 1: return index == n - 1
            nxt_index = set()
            if index == n - 1:  # rule 2
                nxt_index |= pos[t[i + 1]]
            elif s[index + 1] == t[i + 1]:  # rule 0
                nxt_index.add(index + 1)
            if s[0] == t[i + 1]:  # rule 1
                nxt_index.add(0)
            return any(dfs(i + 1, j) for j in nxt_index)

        def path2res(path):
            down, up = [], []
            for i in range(len(path)):
                if path[i] == 0:
                    up.append(i)
                elif i and path[i] - 1 != path[i - 1]:
                    down.append(i - path[i])
            return down[::-1] + up

        if not dfs(0, 0): return []
        return path2res(path)

class Solution:
    def movesToStamp(self, s, t):
        if s[0] != t[0] or s[-1] != t[-1]: return []
        n, m = len(s), len(t)
        path = [0] * m
        pos = collections.defaultdict(set)
        for i, c in enumerate(s): pos[c].add(i)

        def dfs(i, index):
            path[i] = index
            if i == m - 1: return index == n - 1
            nxt_index = set()
            if index == n - 1:  # rule 2
                nxt_index |= pos[t[i + 1]]
            if index < n - 1 and s[index + 1] == t[i + 1]:  # rule 0
                nxt_index.add(index + 1)
            if s[0] == t[i + 1]:  # rule 1
                nxt_index.add(0)
            return any(dfs(i + 1, j) for j in nxt_index)

        def path2res(path):
            down, up = [], []
            for i in range(len(path)):
                if path[i] == 0:
                    up.append(i)
                elif i and path[i] - 1 != path[i - 1]:
                    down.append(i - path[i])
            return down[::-1] + up

        if not dfs(0, 0): return []
        return path2res(path)        

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        done = set()
        n = len(stamp)
        m = len(target)
        candidates = { i for i in range(m-n+1) }
        res = []
        
        def check(i):
            j = 0
            count = 0
            while j < n :
                if i in done:
                    j += 1
                    i += 1
                elif stamp[j] == target[i]:
                    count += 1
                    i += 1
                    j += 1
                else:
                    return -1
            if count == 0:
                return 0
            else:
                return 1
        
        while len(done) < m :
            found = 0
            remove = set()
            for i in candidates:
                I = check(i)
                if I == 1:
                    for j in range(i,i+n):
                        done.add(j)
                    res.append(i)
                    found = 1
                    break
                elif I == 0:
                    remove.add(i)
                    
            if not found:
                return []
            else:
                candidates.remove(i)
                
                    
        return res[::-1]
                
            
        
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        s = set([stamp])
        for i in range(len(stamp)):
            for j in range(len(stamp), i, -1):
                s.add('*'  * i + stamp[i:j] + '*' * (len(stamp) - j))
        print(s)
        
        turns = 0
        numStars = 0
        ans = []
        while turns <= 10 * len(target) and numStars != len(target):
            # print(target)
            replaced = False
            numStars = 0
            for i in range(len(target)):
                if target[i] == '*':
                    numStars += 1
                if i >= len(target) - len(stamp) + 1:
                    continue
                if target[i:i + len(stamp)] in s:
                    ans.append(i)
                    replaced = True
                    target = target[:i] + '*' * len(stamp) + target[i + len(stamp):]
                    break
            if not replaced and numStars != len(target):
                return []
            turns += 1
            
        if turns <= 10 * len(target):
            ans.reverse()
            return ans
        else:
            return []


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        m, n = len(stamp), len(target)
        stamp = list(stamp)
        target = list(target)
        result = []
        
        def change(i):
            if target[i:i + m].count('?') == m:
                return False
            if all(target[i + j] == '?' or target[i + j] == stamp[j] for j in range(m)):
                target[i:i + m] = ['?'] * m
                result.append(i)
                return True
            return False
        while True:
            if not any(change(i) for i in range(n - m + 1)):
                break
        return reversed(result) if target.count('?') == n else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        partial_stamps, L, N = [stamp], len(stamp), len(target)
        for covered_length in range(1, L):
            for leading in range(covered_length+1):
                prefix, postfix = '?'*leading, '?'*(covered_length-leading)
                partial_stamps.append( prefix + stamp[leading:leading+L-covered_length] + postfix )
        
        reversed_positions, dest = [], '?'*N
        while target != dest:
            prev = target
            for idx in range(N-L+1):
                p = target[idx:idx+L]
                for s in partial_stamps:
                    if p == s:
                        reversed_positions.append(idx)
                        target = target[:idx] + '?'*L + target[idx+L:]
                        break
            if prev == target:
                return []
        return reversed_positions[::-1]


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        done = set()
        n = len(stamp)
        m = len(target)
        candidates = { i for i in range(m-n+1) }
        res = []
        
        def check(i):
            j = 0
            count = 0
            while j < n :
                if i in done:
                    j += 1
                    i += 1
                elif stamp[j] == target[i]:
                    count += 1
                    i += 1
                    j += 1
                else:
                    return -1
            if count == 0:
                return 0
            else:
                return 1
        
        while len(done) < m :
            found = 0
            remove = set()
            for i in candidates:
                I = check(i)
                if I == 1:
                    for j in range(i,i+n):
                        done.add(j)
                    res.append(i)
                    remove.add(i)
                    found = 1
                    break
                elif I == 0:
                    remove.add(i)
                    
            if not found:
                return []
            else:
                candidates -= remove
                
                    
        return res[::-1]
                
            
        
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        
        M, N = len(stamp), len(target)
        stamp, target = list(stamp), list(target)
        
        ans = []
        
        def check(i):
            needsUpdate = False
            for j in range(M):
                if target[i+j] == '?':
                    continue
                if target[i+j] != stamp[j]:
                    return False
                needsUpdate = True
            
            if needsUpdate:
                target[i:i+M] = '?' * M
                ans.append(i)
            return needsUpdate
            
        
        changed = True
        while changed:
            changed = False
            for i in range(N - M + 1):
                if check(i):
                    changed = True
                    break

        return ans[::-1] if target.count('?') == len(target) else []
        


class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        pos_detail = []
        complete_cell = [False] * len(target)
        check_next = []
        steps = []
        for i in range(len(target) - len(stamp) + 1):
            match = set()
            unmatch = set()
            for j in range(len(stamp)):
                if target[i + j] == stamp[j]:
                    match.add(i + j)
                else:
                    unmatch.add(i + j)
            pos_detail.append((match, unmatch))
            if not unmatch:
                steps.append(i)
                for j in range(max(0, i - len(stamp) + 1),
                               min(len(target) - len(stamp) + 1, i + len(stamp))):
                    check_next.insert(0, j)
                for j in range(len(stamp)):
                    complete_cell[i + j] = True
        while check_next:
            i = check_next.pop(0)
            match, unmatch = pos_detail[i]
            if not unmatch:
                continue
            for j in range(len(stamp)):
                if i + j in unmatch and complete_cell[i + j]:
                    unmatch.remove(i + j)
            if not unmatch and match:
                steps.insert(0, i)
                for j in range(len(stamp)):
                    complete_cell[i + j] = True
                for j in range(max(0, i - len(stamp) + 1),
                               min(len(target) - len(stamp) + 1, i + len(stamp))):
                    check_next.append(j)
        return steps if all(complete_cell) else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # work backward; time O(n(n-m)); space O(1)
        n_s, n_t = len(stamp), len(target)
        stamp, target = list(stamp), list(target)
        
        def check(idx):
            match = False
            for i in range(n_s):
                if target[idx+i] == '?':
                    continue
                if target[idx+i] != stamp[i]:
                    return False
                match = True
            if match:
                target[idx:idx+n_s] = ['?'] * n_s
                res.append(idx)
            return match
        
        changed = True
        res = []
        while changed:
            changed = False
            for idx in range(n_t-n_s+1):
                changed = changed or check(idx)
        
        return res[::-1] if target == ['?'] * n_t else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # work backward; time O(n(n-m)); space O(1)
        n_s, n_t = len(stamp), len(target)
        stamp, target = list(stamp), list(target)
        
        def check(idx):
            match = False
            for j in range(n_s):
                if target[idx+j] == '?': 
                    continue
                if target[idx+j] != stamp[j]:
                    return False
                match = True
            if match:
                target[idx:idx+n_s] = ['?'] * n_s
                res.append(idx)
            return match
        
        changed = True
        res = []
        while changed:
            changed = False
            for idx in range(n_t - n_s + 1):
                changed = changed or check(idx)
        
        return res[::-1] if target == ['?'] * n_t else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # Time: O(T(T-S)*S); Space: O(S) #
        # We iteratively find the stamp in target and replace the matched string to * 
        # we need to reverse the ans, because the first find ones would be the one that final filled as the assume target at begining is filled with all \"?\"
        # we are filling it back
        
        M, N = len(stamp), len(target)
        stamp = list(stamp)
        target = list(target)
        ans = []
        
        def check(i):
            changed = False
            for j in range(M):
                if target[i+j] == \"?\":
                    continue
                if target[i+j] != stamp[j]:
                    return False
                changed = True
            if changed:
                target[i:i+M] = [\"?\"]*M
                ans.append(i)
            return changed
        
        changed = True
        while changed:
            changed = False
            for i in range(N - M + 1):
                changed = changed or check(i)
        return ans[::-1] if target == [\"?\"]*N else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # work backward
        n_s, n_t = len(stamp), len(target)
        stamp, target = list(stamp), list(target)
        
        def check(idx):
            match = False
            for j in range(n_s):
                if target[idx+j] == '?': 
                    continue
                if target[idx+j] != stamp[j]:
                    return False
                match = True
            if match:
                target[idx:idx+n_s] = ['?'] * n_s
                res.append(idx)
            return match
        
        changed = True
        res = []
        while changed:
            changed = False
            for idx in range(n_t - n_s + 1):
                changed = changed or check(idx)
        
        return res[::-1] if target == ['?'] * n_t else []

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        s,t = list(stamp),list(target)
        n,m = len(s),len(t)
        res = []
        def check(i):
            changed = False
            for j in range(n):
                if t[i+j] == '?':continue
                if t[i+j] != s[j]:return False
                else:
                    changed = True
            if changed:
                t[i:i+n] = ['?']*n
                res.append(i)
            return changed
        chan = True
        while chan:
            chan = False
            for i in range(m-n+1):
                chan = chan or check(i)
        return res[::-1] if t == ['?']*m else []