The Preliminary Contest for ICPC Asia Xuzhou 2019

M Longest subsequence

设dp[i]表示匹配t串的长度为i的前缀需要用到s的最短长度，特别地为了统一，dp[0]=0，INF表示无法匹配。设pos[i][ch]表示在s串的i位置及其以后第一个ch出现的下标。

那么只有两种情况，第一，匹配了长度为i的前缀，然后从第i+1个字符开始严格大，i从0开始，这样就暴力一遍比t[i+1]大的最近的pos就行了。第二，完全匹配t，然后后面有多少加多少，注意至少要加一个！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 1e9;
const int MAXN = 1e6;
char s[MAXN + 5], t[MAXN + 5];
int dp[MAXN + 5];

int pos[MAXN + 5][26];

int main() {
#ifdef local
    freopen("lyz.in", "r", stdin);
#endif // local
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        scanf("%s%s", s + 1, t + 1);
        dp[0] = 0;
        for(int i = 1; i <= m; ++i)
            dp[i] = INF;
        for(int i = 1; i <= m; ++i) {
            for(int j = dp[i - 1] + 1; j <= n; ++j) {
                if(s[j] == t[i]) {
                    dp[i] = j;
                    break;
                }
            }
            if(dp[i] == INF)
                break;
        }

        for(int i = 0; i < 26; ++i)
            pos[n + 1][i] = INF;
        for(int i = n; i >= 1; --i) {
            for(int j = 0; j < 26; ++j)
                pos[i][j] = pos[i + 1][j];
            pos[i][s[i] - 'a'] = i;
        }

        int ans = -1;

        for(int i = 0; i <= m; ++i) {
            int last = INF;
            if(dp[i] == INF)
                break;
            else {
                if(i == m) {
                    if(dp[i] != n)
                        ans = max(ans, i + n - (dp[i] + 1) + 1);
                } else {
                    for(int j = t[i + 1] - 'a' + 1; j < 26; ++j)
                        last = min(last, pos[dp[i] + 1][j]);
                    ans = max(ans, i + n - last + 1);
                }
            }
        }
        printf("%d\n", ans);
    }
}

The Preliminary Contest for ICPC Asia Xuzhou 2019

原文：https://www.cnblogs.com/Inko/p/11483758.html