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    */