1. 戳印序列原题链接

题意：

     题目会给你一个目标序列target和一个印章stamp，现在你可以将序列中的每个字母替换为印章上的相应字母，问怎么替换可以用印章将序列替换为目标序列，如果可以请输出按压的点位顺序；否，则输出空数组{}。

     举个例子，如果初始序列为 "?????"，而你的印章 stamp 是 "abc"，那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc"。（印章必须完全包含在序列的边界内才能盖下去）。

alt

     以上两种情况，都是不可以的。

     注：必须要保证替换能够在10 * target.length 个回合内完成。

做题思路：

     此题初看一脸懵，别急，再看也是一脸懵（不是）。首先我们需要先判断出此题是一道隐藏的拓扑排序题。

     举个例子：这里我们用样例1，当目标序列为ababc，印章为abc时：

i（点） 不相同数
0 1
1 3
2 0

     我们可以当选择不同点进行盖章时，目标序列的子序列和盖章会有不相同的字符，这是因为我们可以对字符进行覆盖，而当字符完全相同，不相同数为0时，就代表该字符是最后盖的。那我们拿开他看看,目标序列变为ab???。

i（点） 不相同数
0 0
1 1
2 0

     此时我们看到又有一个点变为0，从上一个样例可以得到，这说明此时该字符串已经处于最上面，再拿去，目标序列变为?????。

i（点） 不相同数
0 0
1 0
2 0

     诶，对。此时的序列已经变为我们还未盖章的序列了，等等，是不是有点相同？ 我们将不相同数换成in[i]，in数组在拓扑排序中的作用是记录有哪些点链接这个点，而序列子序与印章的对比，恰巧可以构成这份联系。

     综上所诉，我们证实了这道题隐藏的拓扑序列，以下是读入代码：

		int n=target.size();//m代表目标字符串的长度 
        int m=stamp.size();//n代表代表字母印章的长度 
        //为所有目标字符串内印章可印的起始点初始化为m 
        for (int i=0;i<n-m+1;i++)in[i]=m;
        queue<int>q; 
        for (int i=0;i<n-m+1;i++)
        {
            for (int j=0;j<m;j++)
            {
            	//倘若目标字符串和印章字符串相等 
                if (target[i+j]==stamp[j])
                {
                	//假设此处未被覆盖，入度点减一 
                    in[i]--;
                    //当入度为0时，说明此印章在最上方，读入最为起始点 
                    if (!in[i])q.push(i);
                }
                //不相等时，建立起点与该点的边 
                else g[i+j].push_back(i);
            }
        }

     在知道读入后，用基础的拓扑序列就可以得到代码：

		//如果是原先的话，是肯定不用开memset的，毕竟vis初始就是0
		//但它是局域变量（-_-||） ，卡我半天，差评 
        memset(vis,0,sizeof(vis));
        //拓扑排序经典三段走：读点，找点，记点 
        while(!q.empty())
        {
        	//1读点部分 
            int now=q.front();
            q.pop();
            tp.push_back(now);
            //2找点部分 
            //从当前的位置now到now+m中寻找 
            for (int i=0;i<m;i++)
            {
            	//判断该点是否已经覆盖过 
                if (!vis[now+i])
                {
                	//没有的点标记，防止下次读入 
                    vis[now+i]=1;
                    //3记点部分
                    //查找该点的边，并将入度为0的点放入队列 
                    for (auto j:g[now+i])
                    {
                        in[j]--;
                        if (!in[j])q.push(j);
                    }  
                }
            }
        }

     接下来附上完整AC代码：


        const int N=1e6+10;
        int in[N];
        bool vis[N];//利用vis判断数是否已经被覆盖过 
        vector<int>tp;
        vector<int>g[N];
        int n=target.size();//m代表目标字符串的长度 
        int m=stamp.size();//n代表代表字母印章的长度 
        //为所有目标字符串内印章可印的起始点初始化为m 
        for (int i=0;i<n-m+1;i++)in[i]=m;
        queue<int>q; 
        for (int i=0;i<n-m+1;i++)
        {
            for (int j=0;j<m;j++)
            {
            	//倘若目标字符串和印章字符串相等 
                if (target[i+j]==stamp[j])
                {
                	//假设此处未被覆盖，入度点减一 
                    in[i]--;
                    //当入度为0时，说明此印章在最上方，读入最为起始点 
                    if (!in[i])q.push(i);
                }
                //不相等时，建立起点与该点的边 
                else g[i+j].push_back(i);
            }
        }
        //如果是原先的话，是肯定不用开memset的，毕竟vis初始就是0
		//但它是局域变量（-_-||） ，卡我半天，差评 
        memset(vis,0,sizeof(vis));
        //拓扑排序经典三段走：读点，找点，记点 
        while(!q.empty())
        {
        	//1读点部分 
            int now=q.front();
            q.pop();
            tp.push_back(now);
            //2找点部分 
            //从当前的位置now到now+m中寻找 
            for (int i=0;i<m;i++)
            {
            	//判断该点是否已经覆盖过 
                if (!vis[now+i])
                {
                	//没有的点标记，防止下次读入 
                    vis[now+i]=1;
                    //3记点部分
                    //查找该点的边，并将入度为0的点放入队列 
                    for (auto j:g[now+i])
                    {
                        in[j]--;
                        if (!in[j])q.push(j);
                    }  
                }
            }
        } 
        if (tp.size()==n-m+1)
        {
        	//因为从未被覆盖的点查起，所以为最后盖章的点
			//因此需要倒序输出 
            reverse(tp.begin(),tp.end());
            return tp;
        }
        else return {};