专栏首页wym2019亚洲区域赛徐州网络赛 M Longest subsequence

2019亚洲区域赛徐州网络赛 M Longest subsequence

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/100608113

by duhui

记录每一个字母出现位置,贪心找 。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int nex[maxn][26];
char s[maxn],t[maxn];
int ns,nt;
int main() {
	scanf("%d %d",&ns,&nt);
	scanf("%s",s+1);
	scanf("%s",t+1);
	memset(nex,-1,sizeof(nex));
	for(int i=ns-1; i>=0; i--) {
		memcpy(nex[i],nex[i+1],sizeof(nex[i+1]));
		nex[i][s[i+1]-'a'] = i+1;
		//到 第i个位置 往后每个字母第一次出现的位置
	}
	int ans = -1,pos = 0;
	for(int i=1; i<=nt&&pos>=0; ++i) {
		for(int j=t[i]-'a'+1; j<26; ++j) {
			if(nex[pos][j]!=-1) {
				ans = max(ans, ns - nex[pos][j] + 1 + i - 1);//i-1个已经匹配
			}
		}
		pos = nex[pos][t[i]-'a'];//跳到 t[i] 第一次出现的位置
		if(i==nt&&pos!=ns&&pos!=-1) {
			ans = max(ans,nt+ns-pos);
		}
	}
	printf("%d\n",ans);
	return 0;
}
/*
6 6
aaacbc
aaacbc

*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 这些人工智能顶级会议明年移师中国!不出国门也能「华山论剑」

    AI 科技评论按:上周发布的《斯坦福全球 AI 报告》(http://cdn.aiindex.org/2018/AI%20Index%202018%20Annu...

    AI科技评论
  • 入围名单公布!腾讯云IoT应用创新大赛火爆进行中!

    腾讯云IoT应用创新大赛是腾讯云面向物联网领域举办的大型竞赛,通过腾讯云IoT全链路产品能力,开放平台和服务,与广大开发者共同创新,孵化优秀的IoT产品和解决方...

    腾小云
  • 全球超算总决赛融入微软 NLP 赛题,高性能计算和 AI 如何携手前行?

    ASC 世界大学生超级计算机总决赛(ASC18)于近日在南昌大学举行。这个由亚洲超算协会和浪潮集团联合发起的超算竞赛起源于 2012 年,目前已经成功举办7届。...

    AI研习社
  • 2019中国高校计算机大赛网络技术挑战赛正在火热报名中

    中国高校计算机大赛(China Collegiate Computing Contest,简称C4)由教育部高等学校计算机类专业教学指导委员会、教育部高等学校软...

    SDNLAB
  • [人工智能/数据科学比赛]海上风场SCADA数据缺失智能修复

    2019数字中国创新大赛(Digital China Innovation Contest, DCIC 2019)由福建省数字福建建设领导小组办公室、福建省工业...

    统计学家
  • 亚洲国际人工智能+教育大会举办,腾讯WeLearning助力智能教育场景落地

    ? 12月19日,“2019亚洲国际人工智能+教育大会”在厦门举办,腾讯教育运营总经理徐勇群出席并发表了“教育+人工智能探索与践行”的主题演讲。徐勇群从打造人...

    腾讯智慧教育
  • 11冠王清华卫冕失败!中国台湾清华首夺世界大学生超算竞赛冠军,北航破纪录

    此外,北京航空航天大学,在竞赛中的HPL基准测试赛题中,创下每秒50.21万亿次浮点运算性能的成绩,刷新比赛记录。

    量子位
  • 潘淳:苏州.NET俱乐部成立大会全流程-下午(全部22环节)

    ⊙【14】课程2:《使用 .NET Core + DevOps 开发微信跨平台应用》

    寒树Office与RPA
  • 谁还敢说打游戏上不了台面!腾讯电竞正式进入2018亚运会电子体育表演项目

    腾讯大讲堂

扫码关注云+社区

领取腾讯云代金券