文章目录

题目链接：

题意：给两个字符串S和T，在S中找T这个样子的子序列，然后染色，问：能不能把S串都染上色

这题对我来说真难理解，问大佬们都问了好几次。。。。
卡这道题卡了好几天了，心情真郁闷，不够好在现在有点理解了~~~

用一个map记录一哈S串中的每个字符作为最后一个字能匹配到T串中最长到哪里

然后就是我比较难以理解的了：
比如说
abca
abc
当看 s[4]=‘a’ 的时候
这个时候Mp[‘a’]=1
说明 ‘a’ 这个字符才匹配到T串中的第一个字，那说明不行，后面必须有bc来匹配才行

#include"bits/stdc++.h"
using namespace std;
const int maxn=2e5+5;
char s1[maxn],s2[maxn];
int main()
{
	while(cin>>(s1+1)>>(s2+1))
	{
		int N1=strlen(s1+1);
		int N2=strlen(s2+1);
		map<char,int>Mp;
		int now=1;//表示这个字符作为最后一个字符能匹配T串最多到哪里 
		int t=1;//用来看是不是匹配到最后了 
		for(int i=1;i<=N1;i++)
		{
			if(s1[i]==s2[now])Mp[s1[i]]=now++;
			if(s1[i]==s2[t])t++;
			//如果Mp[s[i]]比t小，那就说明又要从前面一点开始匹配 
			t=min(t,Mp[s1[i]]?Mp[s1[i]]+1:0);//这个字符出现过的话就+1 
		}
		if(t<=N2)puts("No");
		else puts("Yes"); 
	}
}