<p>You are given two strings <code>stamp</code> and <code>target</code>. Initially, there is a string <code>s</code> of length <code>target.length</code> with all <code>s[i] == &#39;?&#39;</code>.</p>

<p>In one turn, you can place <code>stamp</code> over <code>s</code> and replace every letter in the <code>s</code> with the corresponding letter from <code>stamp</code>.</p>

<ul>
	<li>For example, if <code>stamp = &quot;abc&quot;</code> and <code>target = &quot;abcba&quot;</code>, then <code>s</code> is <code>&quot;?????&quot;</code> initially. In one turn you can:

	<ul>
		<li>place <code>stamp</code> at index <code>0</code> of <code>s</code> to obtain <code>&quot;abc??&quot;</code>,</li>
		<li>place <code>stamp</code> at index <code>1</code> of <code>s</code> to obtain <code>&quot;?abc?&quot;</code>, or</li>
		<li>place <code>stamp</code> at index <code>2</code> of <code>s</code> to obtain <code>&quot;??abc&quot;</code>.</li>
	</ul>
	Note that <code>stamp</code> must be fully contained in the boundaries of <code>s</code> in order to stamp (i.e., you cannot place <code>stamp</code> at index <code>3</code> of <code>s</code>).</li>
</ul>

<p>We want to convert <code>s</code> to <code>target</code> using <strong>at most</strong> <code>10 * target.length</code> turns.</p>

<p>Return <em>an array of the index of the left-most letter being stamped at each turn</em>. If we cannot obtain <code>target</code> from <code>s</code> within <code>10 * target.length</code> turns, return an empty array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stamp = &quot;abc&quot;, target = &quot;ababc&quot;
<strong>Output:</strong> [0,2]
<strong>Explanation:</strong> Initially s = &quot;?????&quot;.
- Place stamp at index 0 to get &quot;abc??&quot;.
- Place stamp at index 2 to get &quot;ababc&quot;.
[1,0,2] would also be accepted as an answer, as well as some other answers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stamp = &quot;abca&quot;, target = &quot;aabcaca&quot;
<strong>Output:</strong> [3,0,1]
<strong>Explanation:</strong> Initially s = &quot;???????&quot;.
- Place stamp at index 3 to get &quot;???abca&quot;.
- Place stamp at index 0 to get &quot;abcabca&quot;.
- Place stamp at index 1 to get &quot;aabcaca&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= stamp.length &lt;= target.length &lt;= 1000</code></li>
	<li><code>stamp</code> and <code>target</code> consist of lowercase English letters.</li>
</ul>

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

        i = 0
        while i < m and stamp[i] == target[i]:
            i += 1
        top_end = i
        bot_end = m if i == m else 0

        parent = {}
        if top_end > 0:
            parent[(0, top_end)] = ((0, 0), (0, 0))
        if bot_end > 0:
            parent[(1, bot_end)] = ((0, 0), (0, 0))
        
        for i in range(1, n - m + 1):
            # print("i:", i, "top_end:", top_end, "bot_end:", bot_end)
            if bot_end < i and top_end < i:
                return []

            j = 0
            while j < m and stamp[j] == target[i + j]:
                j += 1
            if i + j > top_end:
                s = (0, i + j)
                prev_s = (0, top_end) if top_end >= i else (1, bot_end)
                move = (0, i)
                parent[s] = (prev_s, move)
                top_end = i + j
            if j == m:
                parent[(1, i + j)] = parent[(0, i + j)]
                bot_end = i + j
            elif bot_end >= i:
                j = bot_end - i
                while j < m and stamp[j] == target[i + j]:
                    j += 1
                if j == m:
                    s = (1, i + j)
                    prev_s = (1, bot_end)
                    move = (1, i)
                    parent[s] = (prev_s, move)
                    bot_end = i + j
                elif i + j > top_end:
                    s = (0, i + j)
                    prev_s = (1, bot_end)
                    move = (1, i)
                    parent[s] = (prev_s, move)
                    top_end = i + j
        if bot_end != n:
            return []

        s = (1, n)
        moves = []
        while s in parent:
            prev_s, move = parent[s]
            moves.append(move)
            s = prev_s
        moves = list(reversed(moves))

        ans = [i for t, i in reversed(moves) if t == 1] + [i for t, i in moves if t == 0]
        return ans
17300