# [徐州网络赛]Longest subsequence

[徐州网络赛]Longest subsequence 可以分成两个部分，前面相同，然后下一个字符比对应位置上的大。 枚举这个位置 用序列自动机进行s字符串的下标转移 注意最后一个字符 #include <bits/stdc++.h> const int maxn = 1e6 + 7; using namespace std; #define ll long long int n, m; char

# [徐州网络赛]Longest subsequence

```#include <bits/stdc++.h>

const int maxn = 1e6 + 7;
using namespace std;
#define ll long long
int n, m;
char s[maxn], t[maxn];
int nex[maxn][27];

void init() {
for (int k = 0; k < 26; ++k) nex[n][k] = -1;
for (int i = n; i >= 1; --i) {
for (int k = 0; k < 26; ++k) {
nex[i - 1][k] = nex[i][k];
}
nex[i - 1][s[i] - 'a'] = i;
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
cin >> s + 1 >> t + 1;
int minn;
int ans = 0;
int i, j;
init();
for (j = 0, i = 0; j <= m; ++j) {
minn = 1e9;
for (int k = max(0, t[j + 1] - 'a' + 1); k < 26; ++k) {
if (nex[i][k] != -1) {
minn = min(nex[i][k], minn);
}
}
if (minn != 1e9) {
ans = max(ans, n - minn + 1 + j);
}
if (j == m) break;
i = nex[i][t[j + 1] - 'a'];
if (i == -1) {
break;
}
}
if (ans == 0) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}```