[徐州网络赛]Longest subsequence

可以分成两个部分，前面相同，然后下一个字符比对应位置上的大。

枚举这个位置

用序列自动机进行s字符串的下标转移

注意最后一个字符

#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;

}

巴特西

[徐州网络赛]Longest subsequence

[徐州网络赛]Longest subsequence

最新文章

热门文章