936. Stamping The Sequence Hard

1/**
2 * [936] Stamping The Sequence
3 *
4 * You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'.
5 * In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp.
6 * 
7 * 	For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:
8 * 	
9 * 		place stamp at index 0 of s to obtain "abc??",
10 * 		place stamp at index 1 of s to obtain "?abc?", or
11 * 		place stamp at index 2 of s to obtain "??abc".
12 * 	
13 * 	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).
14 * 
15 * We want to convert s to target using at most 10 * target.length turns.
16 * 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.
17 *  
18 * Example 1:
19 * 
20 * Input: stamp = "abc", target = "ababc"
21 * Output: [0,2]
22 * Explanation: Initially s = "?????".
23 * - Place stamp at index 0 to get "abc??".
24 * - Place stamp at index 2 to get "ababc".
25 * [1,0,2] would also be accepted as an answer, as well as some other answers.
26 * 
27 * Example 2:
28 * 
29 * Input: stamp = "abca", target = "aabcaca"
30 * Output: [3,0,1]
31 * Explanation: Initially s = "???????".
32 * - Place stamp at index 3 to get "???abca".
33 * - Place stamp at index 0 to get "abcabca".
34 * - Place stamp at index 1 to get "aabcaca".
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	1 <= stamp.length <= target.length <= 1000
40 * 	stamp and target consist of lowercase English letters.
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/stamping-the-sequence/
46// discuss: https://leetcode.com/problems/stamping-the-sequence/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn moves_to_stamp(stamp: String, target: String) -> Vec<i32> {
52        vec![]
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_936() {
64    }
65}
66