C++14(g++5.4) 解法, 执行用时: 33ms, 内存消耗: 604K, 提交时间: 2020-05-30 13:42:55

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main() {
    string text, pattern;
    cin >> text >> pattern;

    int n = text.size();
    int m = pattern.size();

    for (int i = 0; i < n; ++i) {
        text[i] -= 'a';
    }
    
    for (int i = 0; i < m; ++i) {
        pattern[i] -= 'a';
    }

    vector<vector<int> > next(m, vector<int>(26, 0));

    for (int i = 1; i < m; ++i) {
        int prev = next[i - 1][pattern[i - 1]];
        next[i - 1][pattern[i - 1]] = i;
        for (int j = 0; j < 26; ++j) {
            next[i][j] = next[prev][j];
        }
    }
    next[m - 1][pattern[m - 1]] = m;

    vector<int> max_taken(m, -n - 1);
    max_taken[0] = 0;
    for (int i = 0; i < n; ++i) {
        vector<int> next_taken = max_taken;
        for (int j = 0; j < m; ++j) {
            int cur = next[j][text[i]];
            if (cur < m) {
                next_taken[cur] = max(next_taken[cur], max_taken[j] + 1);
            }
        }
        max_taken = next_taken;
    }

    int result = 0;
    for (int i = 0; i < m; ++i) {
        result = max(result, max_taken[i]);
    }

    cout << n - result << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 54ms, 内存消耗: 504K, 提交时间: 2020-06-01 14:08:20

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;
string S, s;
int n, m, nxt[N][30], dp[N], f[N];
int main() {
    cin >> S >> s;
    n = S.size(), m = s.size();
    for (int i = 0; i < n; i++) S[i] -= 'a';
    for (int i = 0; i < m; i++) s[i] -= 'a';
    for (int i = 1; i < m; i++) {
        int pr = nxt[i - 1][s[i - 1]];
        nxt[i - 1][s[i - 1]] = i;
        for (int j = 0; j < 26; j++) nxt[i][j] = nxt[pr][j];
    }
    nxt[m - 1][s[m - 1]] = m, dp[0] = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j++) {
            int cur = nxt[j][S[i]];
            f[cur] = max(f[cur], dp[j] + 1);
        }
        memcpy(dp, f, sizeof dp);
    }
    int res = 0;
    for (int i = 0; i < m; i++) res = max(res, dp[i]);
    cout << n - res;
    return 0;
}