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 即可（逆序分析）。相反，我们返回一个空容器。最后根据容器大小ac这道题

ac代码

// Problem: E - Stamp
// Contest: AtCoder - Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 329）
// URL: https://atcoder.jp/contests/abc329/tasks/abc329_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>

using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define endl "\n"
#define pb push_back
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;

void solve()
{
    int n, m; cin >> n >> m;
    string s, t; cin >> s >> t;
    vector<vector<int>> g(n);
    vector<int> ind(n - m + 1, m);
    vector<int> q;
    vector<bool> st(n);
    for(int i = 0; i < n - m + 1; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(s[i + j] == t[j])
            {
                ind[i] --;
                if(ind[i] == 0) q.pb(i);
            }
            else
                g[i + j].pb(i);
        }
    }
    vector<int> res;
    while(q.size())
    {
        int u = q.back(); q.pop_back();
        res.pb(u);
        for(int i = 0; i < m; i ++)
        {
            if(st[u + i]) continue;
            st[u + i] = true;
            for(auto &&v : g[u + i])
            {
                ind[v] --;
                if(ind[v] == 0) q.pb(v);//插到u后面，可以改变v窗口的元素
            }
        }
    }
    reverse(res.begin(), res.end());//正确的顺序
    //for(auto it : res) cout << it << ' ';
    if(res.size() < n - m + 1) cout << "No" << endl;
    else cout << "Yes" << endl;
}
int main()
{
        solve();
    return 0;
}