Codeforces Round #579 (Div. 3) D2. Remove the Substring (hard version)
发布日期:2021-06-29 14:25:17
浏览次数:2
分类:技术文章
本文共 755 字,大约阅读时间需要 2 分钟。
题目大意
给出一段长串s1和它的一段非连续子串s2,求s1最长的连续删除区间,使得s2仍为s1的非连续子串
题解
最大分割情况只可能是两种,一种是最左端或者最右端删去一大段,另一种是中间任意两个字母间删去一大段
①先看第一种,那么肯定是要找到s2在s1中的最左相同点和最右相同点,很简单
②另一种,删去的区间端点两个字母肯定是s2中相邻的字母,即保证删去中间一段没用的,仍是子串 例如s1:abbccbbbcccddde s2: ab 那么最长区间肯定是找到s1最左端满足条件的a,再找到s1最右端满足条件的b,中间都是可以删的,如果s2:abd 就找到s1最左端满足条件的b,再找到s1最右端满足条件的d,作差值,然后取max
#includeusing namespace std;const int maxn=2e5+5;char s[maxn],t[maxn];int pre[maxn],bac[maxn];int main(){ scanf("%s",s); scanf("%s",t); int lens=strlen(s); int lent=strlen(t); int j=0; for(int i=0;i =0&&j>=0;i--){ if(s[i]==t[j]) bac[j--]=i; } int kmax=max(max(pre[0],lens-1-pre[lent-1]),max(bac[0],lens-1-bac[lent-1]));//第一种情况 for(int i=1;i
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/100106762 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月30日 05时19分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python抓取哔哩哔哩up主信息:只要爬虫学的好,牢饭吃的早
2019-04-29
有个码龄5年的程序员跟我说:“他连wifi从来不用密码”
2019-04-29
领导让我整理上个季度的销售额,幸好我会Python数据分析,你猜我几点下班
2019-04-29
【Python爬虫实战】为何如此痴迷Python?还不是因为爱看小姐姐图
2019-04-29
零基础自学Python,你也可以实现经济独立!
2019-04-29
数字化转型的主干道上,华为云以“三大关键”成企业智能化推手
2019-04-29
数字化为何不走“捷”“径”?
2019-04-29
和总裁、专家交朋友,华为云助推政企智能化升级又做到前面去了
2019-04-29
BCOP章鱼船长,6月22日晚上8点上线薄饼
2019-04-29
为战疫助力,半导体功不可没
2019-04-29
了解这些操作,Python中99%的文件操作都将变得游刃有余!
2019-04-29
知道如何操作还不够!深入了解4大热门机器学习算法
2019-04-29
只有经历过,才能深刻理解的9个编程道理
2019-04-29
发现超能力:这些数据科学技能助你更高效专业
2019-04-29
AI当道,人工智能将如何改变金融业?
2019-04-29
消除性别成见,技术领域需要更多“乘风破浪的姐姐”
2019-04-29
7行代码击败整个金融业,这对20多岁的爱尔兰兄弟是如何做到的?
2019-04-29
2020十大编程博客:私藏的宝藏编程语言博客大放送!
2019-04-29
编程中的角色选择:哪类工作角色最适合你?
2019-04-29