# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/greedy/936.-stamping-the-sequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.