rt,感觉在dp时加一个记忆化正确性没有保证，但是跑的飞快。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e4 + 5;
char a[N], s[N];
int ne[N], f[2][N];
int main(){
    scanf("%s %s", s + 1, a + 1);
    int j = 0, len1 = strlen(s + 1), len2 = strlen(a + 1);
    for(int i = 2; i <= len2; i++){
        while(j && a[i] != a[j + 1]) j = ne[j];
        if(a[i] == a[j + 1]) j++;
        ne[i] = j;
    }
    for(int i = 1; i <= len1; i++){
        for(int j = 0; j <= len2; j++) f[i&1][j] = f[(i - 1)&1][j];
        for(int j = 0; j < len2; j++){
            int k = j;
            while(k && s[i] != a[k + 1]) k = ne[k];
            if(k != j) ne[j] = k;
            if(a[k + 1] == s[i]) k++;
            f[i&1][k] = max(f[(i - 1)&1][j] + 1, f[i&1][k]);
        } 
    }
    int ans = 0;
    for(int i = 0; i < len2; i++) ans = max(ans, f[len1&1][i]);
    printf("%d", len1 - ans);
    return 0;
}