E-Stamp是什么？

题目链接 ：E - Stamp (atcoder.jp) 题意：给定长为n的s串，m的t串，和一个长度为n的x串，问你能否操作任意次数的操作， 每次操作都可以使x中长度为m的存在串变为t，最后使得变为n 赛时没过，赛后有人发了原题，936. 戳印序列 - 力扣（LeetCode），看了很久的题解，发现做法太巧妙了，把字符串转化为(图论)拓扑图，属实想不到， 最后还能求出可以操作哪些位置 思路：因为前面的操作会影响后面的操作，所以要考虑倒推 本文采用类似于拓扑排序的思想。 我们记字母印章长度为 m ，目标字符串长度为 n 。我们拿字母印章在目标字符串上进行滑动，那么在目标字符串中总共将会有 n−m+1 个窗口。另外，我们将逆序操作过程中所得到的各窗口的起始端点值记录在列表 res 中，最后只需将 res 反转即可得到答案。 那么我们可以将本题和拓扑排序的相关概念进行映射： >「入度」：每个窗口中对应字符不相同的总数，起始默认为 m。当入度为 0 时，说明这个窗口的所有字符都与目标字符串相对应，我们就可以把这个窗口放入到队列（不一定是 vector 的队列，任意容器均可, deque也可以）中。 >「边」：对于目标字符串的每个位置上，有不一致字符的窗口。我们用邻接表的方式存储边，如果一个滑动窗口的某一个字符与目标字符串不一致，那么我们就连一条边。 至此，我们通过拓扑排序，就可以得到最终的结果了： 1.遍历一遍所有的窗口，如果该位置上的字符与目标字符不一致，那么我们在邻接表中连接一条边；相反如果字符一致，那么该窗口的入度减 1。 2.当某个窗口的入度为 0 时，那么这个窗口的所有字符都与目标字符串相对应，我们可以将该窗口的起始端点放入到队列中。 3.将队列中的窗口依次出队，每次出队时，我们在 res 列表中记录该窗口的起始端点。 4.我们可以想象该窗口中的字符全部替换为 '#' ，表示可以匹配任意字符。那么我们可以从邻接表中将之前与该位置不同的窗口的入度都减 1。 5.重复（2），直到队列为空。 6.当队列为空时，判断 res 的长度是否与 n−m+1 相等，相等则完成了拓扑排序；不相等则说明无法印出目标字符串。 7.如果完成了拓扑排序，那么 res 的长度一定是符合题目要求，我们只需返回逆序的 res 即可（逆序分析）。相反，我们返回一个空容器。