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: MEDIUM
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

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

Solutions:
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]:
		(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


class Solution:

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

		def check(i):
			found = False
			for j in range(len(s)):
				if t[i + j] == '*':
					continue
				if t[i + j] != s[j]:
					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):
			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 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):
					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(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):
					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):
				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]:
				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]:
		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:
			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]


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:
				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:
						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:

	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):
			(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 not todo:
				ans.append(i)
				for j in range(i, i + len(stamp)):
					if not done[j]:
						queue.append(j)
						done[j] = True
		while queue:
			i = queue.popleft()
			for j in range(max(0, i - M + 1), min(N - M, i) + 1):
				if i in A[j][1]:
					A[j][1].discard(i)
					if not A[j][1]:
						ans.append(j)
						for m in A[j][0]:
							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]:
		(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)]
		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
		return ret[::-1] if cnt == len(target) else []


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]:
		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
					idx = target.find(cur_stamp)
					while idx != -1:
						target = target[:idx] + '*' * len(cur_stamp) + target[idx + len(cur_stamp):]
						res.append(idx)
						cur_len += len(stamp) - i - j
						idx = target.find(cur_stamp)
			all_len += cur_len
		return res[::-1] if all_len == len(target) else []


class Solution:

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

		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]:
		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
				elif 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 []


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 = 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
		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]:

		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]:
		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]:
		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]:
		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()
		v = [set() for _ in range(lent - lens + 1)]
		t = [set() for _ in range(lent - lens + 1)]
		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]:
		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)
		while que:
			win_start = que.popleft()
			for nws in range(max(0, win_start - M + 1), min(nwin, win_start + M)):
				if nws in done:
					continue
				for pos in range(win_start, win_start + M):
					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):
		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: 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]:
		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
			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, 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:
				nxt_index |= pos[t[i + 1]]
			elif s[index + 1] == t[i + 1]:
				nxt_index.add(index + 1)
			if s[0] == t[i + 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, 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):
			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]:
		(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]:
		(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 []