Revise paste dc2829ad9aa7c

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define boAshraf { ios_base::sync_with_stdio(false); cin.tie(NULL); }
#define ll long long
#define sz(s) (int)(s).size()
#define endl "\n"
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

void File();
void sol();
int  f[(int)1e5+5];
void KMP(const string&pat){
    int len = 0;
    f[0] = 0;
    for (int i = 1; i < pat.size(); ++i) {
        while (len>0 && pat[i] != pat[len])
            len = f[len - 1];
        if (pat[i] == pat[len])
            ++len;
        f[i] = len;
    }
}
vector<vector<int>>aut;
void compute_automaton(string s) {
    s += '#';
    int n = s.size();
    aut.assign(n, vector<int>(27));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[f[i - 1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
            aut[i][26]=max(aut[i][c],aut[i][26]);
        }
    }
}
string pat,s;
const int N=1e4,M=1e3;
int n,m;
int idd;
int dp[N][M];
int vis[N][M];
int rec(int i,int match){
    if(match==m)return 1e9;
    if(i==n)return 0;
    int &ret=dp[i][match];
    if(vis[i][match]==idd)return ret;
    vis[i][match]=idd;
    ret=1e9;
    if(s[i]==pat[match]){
        ret=min(rec(i+1,match)+1,rec(i+1,match+1));
    }
    int sz=aut[match][s[i]-'a'];
    ret= min(ret,rec(i+1,sz));
    return ret;
}
int main() {
    boAshraf
    File();
    int t = 1;
    //cin >> t;
    while (t--) {
        sol();
    }
    return 0;
}
void sol() {
    while(cin>>s>>pat){
        KMP(pat);
        compute_automaton(pat);
        n=s.size();m=pat.size();
        ++idd;
        cout<<rec(0,0)<<endl;
    }
}

void File() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}