C

// ConsoleApplication3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <string>
#include <map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

const ll S = 10010;
const ll T = 1010;
const ll INF = 1e12;

str s, t;
ll dp[S][T], nx[S];
map <char, int> mp;

ifstream in;
ofstream out;

int main()
{
    in.open("input.txt");
    out.open("output.txt");
    in >> s >> t;
    for (int i = 0; i < s.size(); i++)
        for (int j = 0; j < t.size(); j++)
            dp[i][j] = INF;
    if (s[0] == t[0])
        dp[0][0] = 1;
    for (int i = 1; i < s.size(); i++)
        for (int j = 0; j < t.size(); j++)
            if (j != 0)
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j] + (s[i] == t[j] ? 1 : 0));
            else
                dp[i][j] = dp[i - 1][j] + (s[i] == t[j] ? 1 : 0);
    for (int i = 0; i < s.size(); i++, out << endl)
        for (int j = 0; j < t.size(); j++)
            out << dp[i][j] << ' ';
    ll mn = 0;
    for (int i = 0; i < t.size(); i++)
        if (dp[s.size() - 1][i] < dp[s.size() - 1][mn])
            mn = i;
    cout << mn << endl;
    system("pause");
    return 0;
}

/*
abacaba
aba
*/