codeforce 223B B. Two Strings

文章目录

题目链接:

题意:给两个字符串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"); 
	}
}
全部评论

相关推荐

02-16 01:39
南昌大学 Java
重剑Ds:感觉不太可能 后端都减飞了 根本不缺人
点赞 评论 收藏
分享
刚刷到字节跳动官方发的消息,确实被这波阵仗吓了一跳。在大家还在纠结今年行情是不是又“寒冬”的时候,字节直接甩出了史上规模最大的转正实习计划——ByteIntern。咱们直接看几个最硬的数,别被花里胡哨的宣传词绕晕了。首先是“量大”。全球招7000多人是什么概念?这几乎是把很多中型互联网公司的总人数都给招进来了。最关键的是,这次的资源分配非常精准:研发岗给了4800多个Offer,占比直接超过六成。说白了,字节今年还是要死磕技术,尤其是产品和AI领域,这对于咱们写代码的同学来说,绝对是今年最厚的一块肥肉。其次是大家最关心的“转正率”。官方直接白纸黑字写了:整体转正率超过50%。这意味着只要你进去了,不划水、正常干,每两个人里就有一个能直接拿校招Offer。对于2027届(2026年9月到2027年8月毕业)的同学来说,这不仅是实习,这简直就是通往大厂的快捷通道。不过,我也得泼盆冷水。坑位多,不代表门槛低。字节的实习面试出了名的爱考算法和工程实操,尤其是今年重点倾斜AI方向,如果你简历里有和AI相关的项目,优势还是有的。而且,转正率50%也意味着剩下那50%的人是陪跑的,进去之后的考核压力肯定不小。一句话总结:&nbsp;27届的兄弟们,别犹豫了。今年字节这是铁了心要抢提前批的人才,现在投递就是占坑。与其等到明年秋招去千军万马挤独木桥,不如现在进去先占个工位,把转正名额攥在手里。
喵_coding:别逗了 50%转正率 仔细想想 就是转正与不转正
字节7000实习来了,你...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务