Codeforces-1492 C. Maximum width（构造）

思路：
存下$s$字符串中每个字母的位置；从前往后考虑，对于$t$字符串的每个位置依次寻找这个字母最近的大于上一次的位置。
这样得到一个可行的$p$序列。
我们要求最大间隔，所以可以从后往前考虑，找到$t$中每个位置最后一个小于下一次的位置，然后算出当前和之前的差值，就是对于$i$这个位置能得到的$p[i]-p[i-1]$最大值。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
char s[maxn],t[maxn];
vector<int>G[100];
int p[maxn];
int get(int ch,int x) { //第一个大于xreturn *upper_bound(G[ch].begin(),G[ch].end(),x);
}
int get2(int ch,int x) { //最后一个小于xreturn *--lower_bound(G[ch].begin(),G[ch].end(),x);
}
int main() {int n,m;scanf("%d%d",&n,&m);scanf("%s%s",s + 1,t + 1);for(int i = 1;i <= n;i++) {int ch = s[i] - 'a';G[ch].push_back(i);}int pre = 0;int ans = 0;for(int i = 1;i <= m;i++) {int ch = t[i] - 'a';p[i] = get(ch,pre);pre = p[i];}int nex = 1e9;for(int i = m;i >= 2;i--) {int ch = t[i] - 'a';int num = get2(ch,nex);p[i] = num;nex = num;ans = max(ans,p[i] - p[i - 1]);}printf("%d\n",ans);return 0;
}