人の手でこの問題を解くときには、「この部分とこの部分が似てそうだからここを重ねたら良さそう！」みたいに考えるかと思いますが、そうした考えをプログラムに落とし込むのは難しいです。

今回は、\(S\) ,\(T\) の文字数に関する制約があまり大きくないので、\(S\) の何文字目と \(T\) の \(1\) 文字目を重ねるかを全探索しても、十分間に合います。全てのパターンにおいて、変更の必要な文字数を求め、その最小値を答えることで、今回の問題を解くことが出来ます。

計算量は、\(S\) の何文字目に重ねるかのパターンが \(O(|S|)\)、それぞれのパターンにおいて、何文字変更しなければならないかを求めるのに必要な計算量は、\(T\) 文字分なので\(O|T|)\) となり、あわせて \(O(|S||T|)\) となります。（\(|S|\) は、\(S\) の文字数とします。）

回答例(C++)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	string S, T;
	cin >> S >> T;

	//答えansを仮置きする。
	//これが十分に大きくないと不正解となるので、
	//この値なら絶対に正しい答えが出る、という値を仮置きすること
	int ans = T.size();

	//Sの何文字目から調べるかを全探索する
	for (int start = 0; start <= S.size() - T.size(); start++)
	{
		int diff = 0;
		for (int i = 0; i < T.size(); i++)
		{
			if (T[i] != S[start + i]) {
				diff++;
			}
		}
		ans = min(ans, diff);
	}

	cout << ans << endl;
}