https://nanti.jisuanke.com/t/41395

题意：给定s和t 寻找s的子序列 目标子序列字典序大于t 如果不存在输出-1 否则输出字符串的长度。。。
题解：有一说一 这个题看了半天我还是不会 半会不会的 还差很多东西阿
copy一份题解思路

对于答案来说，一定是

1. 前 i-1 个字符和 t的前 i 个一样，然后第 i 个字符比 t的 大 i∈[1,m]i∈[1,m]
2. 前缀为t，然后长度比t长

对于第一种情况，枚举这个 i ，然后找最小的 p 可以使得从s[1∼p] 中产生t1t2⋯ti−1 ,然后在s[p+1,n]中找最左边的比t[i] 大的字符，假如 找到了s[pos]，那么后面的s[pos+1,n] 都可以加到答案后面（因为s[pos]>t[i] 已经保证答案大于t了)

对于第二种，根据求第一种的方法，不难求出

如何找最小的p？预处理一个sf[i][c] 数组，表示s[i] 后面第一个字符c在哪里即可

如何找pos? 也是用预处理的数组循环最多26次即可

原帖：https://www.cnblogs.com/1625--H/p/11482455.html

AC代码：

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
const int maxn = 1e6 + 5;
int sf[maxn][26];//s[i]后面第一个字符c在哪里

char s[maxn], t[maxn];

int n, m;

int main() {
	ios::sync_with_stdio(0);
	scanf("%d%d", &n, &m);
	scanf("%s%s", s + 1, t + 1);
	for (int i = 0; i < 26; i++) {//最后一个字符后面出现的每个字母的位置初始化为n+1;
		sf[n][i] = n + 1;
	}
	for (int i = n - 1; i >= 0; i--) {//之后从后往前遍历开始处理s的每一位
		memcpy(sf[i], sf[i + 1], sizeof(sf[i]));//复制后一个的情况
		sf[i][s[i + 1] - 'a'] = i + 1;//更新后面那个
	}
	int p = 0;//最小的p可以使得从s[1-p]中产生t1t2...ti-1
	int res = -1;
	for (int i = 1; i <= m; i++) {
		int pos = n + 1;//默认在最后一个;
		for (int j = t[i] - 'a' + 1; j < 26; j++) {
			pos = min(pos, sf[p][j]);//找严格比t这位大的最近的 s[pos]>t[i]
		}
		if (pos != n + 1) {
			res = max(res, i + n - pos);//(n-pos)为后面还可以加的长度 就是全加 i是相同前缀
		}
		p = sf[p][t[i] - 'a'];//更新p的位置
		if (p == n + 1) break;
	}
	if (p < n) {
		res = max(res, n - p + m);
	}
	printf("%d\n", res);
	return 0;
}