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

• 2019 年 10 月 4 日
• 筆記

版权声明：本文为博主原创文章，遵循 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("%dn",ans);  	return 0;  }  /*  6 6  aaacbc  aaacbc    */