You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'.

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


	For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:

	
		place stamp at index 0 of s to obtain "abc??",
		place stamp at index 1 of s to obtain "?abc?", or
		place stamp at index 2 of s to obtain "??abc".
	
	Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).


We want to convert s to target using at most 10 * target.length turns.

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

&nbsp;
Example 1:

Input: stamp = "abc", target = "ababc"
Output: [0,2]
Explanation: Initially s = "?????".
- Place stamp at index 0 to get "abc??".
- Place stamp at index 2 to get "ababc".
[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]
Explanation: Initially s = "???????".
- Place stamp at index 3 to get "???abca".
- Place stamp at index 0 to get "abcabca".
- Place stamp at index 1 to get "aabcaca".


&nbsp;
Constraints:


	1 &lt;= stamp.length &lt;= target.length &lt;= 1000
	stamp and target consist of lowercase English letters.


class Solution:
    def movesToStamp(self, S: str, T: str) -> List[int]:
        if S == T: return [0]
        S, T = list(S), list(T)
        slen, tlen = len(S), len(T) - len(S) + 1
        ans, tdiff, sdiff = [], True, True
        while tdiff:
            tdiff = False
            for i in range(tlen):
                sdiff = False
                for j in range(slen):
                    if T[i+j] == "*": continue
                    if T[i+j] != S[j]: break
                    sdiff = True
                else: 
                    if sdiff:
                        tdiff = True
                        for j in range(i, i + slen): T[j] = "*"
                        ans.append(i)
        for i in range(len(T)):
            if T[i] != "*": return []
        return reversed(ans)
class Solution {
    public int[] movesToStamp(String stamp, String target) {
        
        /*
        * Intitution:
        * Instead of creating target string from intial state,
        * create the intial state from the target string.
        * - take a window of stamp length
        * - reverse that window to the intail state 
        *  current state -> abcdefgh, window = def, 
        *  next state    -> abc???gh 
        *
        */
        
        int sLen = stamp.length();
        int tLen = target.length();
        
        //it save the index of reversed charcacter
        Queue<Integer> reversedCharIndices= new LinkedList();
        
        //it mark Character of target, as reversed
        boolean[] isReversedCharOfThisIndex = new boolean[tLen];
        
        Stack<Integer> stack = new Stack();
        
        List<Window> widowList = new ArrayList();
        
        for(int windowStartIndex = 0; windowStartIndex <= tLen - sLen; windowStartIndex++){
            
            Set<Integer> matched = new HashSet();
            Set<Integer> notMatched = new HashSet();
            
            for(int j = 0; j < sLen; j++){
                
                //char index of current window of the target
                int charIndex = windowStartIndex + j;
                
                if(stamp.charAt(j) == target.charAt(charIndex)){
                    matched.add(charIndex);
                } else {
                    notMatched.add(charIndex);
                }
            }
            
            //add the window
            widowList.add(new Window(matched, notMatched));
            
            //when all char of current window is matched with 
            if(notMatched.isEmpty()){
                stack.push(windowStartIndex);
                
                for(int index : matched){
                    if(!isReversedCharOfThisIndex[index]){
                        
                        //add in queue, so that we can process,
                        //another window which is affected by its character get reversed
                        reversedCharIndices.add(index);
                        
                        //mark it reversed
                        isReversedCharOfThisIndex[index] = true;
                    }
                }
                
            }
        }
        
        
        
        //get all char index, one by once
        //see the impact of reverse char of this index, in ano
        while(!reversedCharIndices.isEmpty()){
            int reversedCharIndex = reversedCharIndices.remove();
            
            int start =  Math.max(0, reversedCharIndex - sLen + 1);
            int end   =  Math.min(reversedCharIndex, tLen - sLen);
            
            for(int windowIndex = start; windowIndex <= end; windowIndex++){
                
                if(widowList.get(windowIndex).notMatched.contains(reversedCharIndex)){
                    
                   
                    //as this char is reversed in another window
                    //remove this char index from current window, 
                    widowList.get(windowIndex).notMatched.remove(reversedCharIndex);
                    
                    if(widowList.get(windowIndex).notMatched.isEmpty()){
                        
                        //as all of charcater reversed of current window
                        //now add current window index
                        stack.push(windowIndex);
                        
                        for(int index : widowList.get(windowIndex).matched){
                            
                            if(!isReversedCharOfThisIndex[index]){

                                //add in queue, so that we can process,
                                //another window which is affected by its character get reversed
                                reversedCharIndices.add(index);

                                //mark it reversed
                                isReversedCharOfThisIndex[index] = true;
                            }
                        }
                    }
                }
                
            }
        }
        
            
        for(boolean reversed : isReversedCharOfThisIndex){
            if(!reversed){
                return new int[0];
            }
        }
        
        int i = 0;
        int[] result = new int[stack.size()];
        while(!stack.empty()){
            result[i++] = stack.pop();
        }
        
        
        return result;
        
    }
}

class Window {
    Set<Integer> matched;
    Set<Integer> notMatched;
    
    public Window(Set<Integer> matched, Set<Integer> notMatched){
        this.matched = matched;
        this.notMatched = notMatched;
    }
}
class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        auto isUndone = [](auto it, auto endIt) {
            return all_of(it, endIt, [](char c) { return c == '?'; });
        };
        vector<int> res;

        while (!isUndone(begin(target), end(target))) {
            auto prevResSize = size(res);

            for (size_t i = 0; i < size(target) - size(stamp) + 1; ++i) {
                auto it = begin(target) + i, endIt = it + size(stamp);
                if (isUndone(it, endIt))
                    continue;

                size_t j = 0;
                for (; j < size(stamp) && (*(it + j) == stamp[j] || *(it + j) == '?'); ++j);

                if (j == size(stamp)) {
                    fill(it, endIt, '?');
                    res.push_back(i);
                }
            }
            if (prevResSize == size(res))
                return {};
        }

        reverse(begin(res), end(res));
        return res;
    }
};
var movesToStamp = function(stamp, target) {
    var s = target.replace(/[a-z]/g,"?")
    var repl = s.substr(0,stamp.length)
    let op = []
    let s1 = target

    while(s1 !== s){
        let idx = getIndex()
        if(idx === -1) return []
        op.push(idx)
    }
    return op.reverse()
    
    function getIndex(){
        for(let i=0; i<target.length; i++){
            let match = 0
            let j=0
            for(; j<stamp.length; j++){
                if(target.substr(i+j,1) === stamp.substr(j,1)) match++
                else 
                    if(target.substr(i+j,1) === "?") continue
                else break
            }

            
            if(j===stamp.length && match!==0){
                let k=i
                for(let j=0; j<stamp.length; j++){
                    if(k===0){ s1 = "?"+target.substr(1)}
                    else {     s1 = target.substr(0,k)+"?"+target.substr(k+1)}
                    k++
                    target = s1
                }
                return i
            }
        }
    
    return -1
    }
};
    
    
    ```
Stamping The Sequence