> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/greedy/936.-stamping-the-sequence.md).

# 936. Stamping The Sequence

给定两个字符串S和T，在一个长为T的空间，把S当章敲，即可以不断从空间内任何位置开始覆盖成S，问最后能否敲出T。正着DFS模拟敲章过程时间复杂度会非常高。反过来想，如果能敲成功，最后一次敲的一定是S，那就可以从T中搜索S所在位置把对应的所有字符打上\*，意味着它们之前随意怎么敲都无所谓。再对剩下的可能的起始位置做类似的搜索，实际上只要满足除去\*后和T有交集就可以作为倒数第二步，依次类推。最后得出来的就是反过来的敲章过程。这么得出的过程并不一定是最短的敲章过程。

![](https://pic4.zhimg.com/80/v2-328749337be34e047f4e26cde2ab835f_hd.jpg)

答案参考自[花花](https://link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3DOQi4n8EKRD8)。

```cpp
/*
 * @lc app=leetcode id=936 lang=cpp
 *
 * [936] Stamping The Sequence
 */

// @lc code=start
class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        const int N = target.length(), M = stamp.length();
        vector<int> res;
        vector<bool> visited(N);
        int total = 0;
        const auto un_stamp = [&](int s) {
            int l = M;
            for (int i = 0; i < M; ++i) {
                if (target[s + i] == '*') --l;
                else if (target[s + i] != stamp[i]) return 0;
            } 
            if (l != 0) fill(begin(target) + s, begin(target) + s + M, '*');
            return l;
        };
        while (total < N) {
            bool found = false;
            for (int i = 0; i <= N - M; ++i) {
                if (visited[i]) continue;
                int l = un_stamp(i);
                if (l == 0) continue;
                visited[i] = true;
                total += l;
                res.push_back(i);
                found = true;
            }
            if (!found) return {};
        }
        reverse(begin(res), end(res));
        return res;
    }
};
// @lc code=end
```