[백준][C++] 1120: 문자열

문제 링크: https://www.acmicpc.net/problem/1120

 

B를 고정시켜놓고 A를 적당히 움직이면서 차이의 최소를 찾으면 됩니다. 왜냐면 앞뒤로 채우는 알파벳은 아무거나 채울 수 있으니 B와 동일한 알파벳을 추가한다고 가정하면 차이가 늘지 않기 때문입니다.

 

A=abc, B=aabbaabb라고 해보면 이런식으로 반복문을 돌리면 되겠죠?

 

#include <bits/stdc++.h>
using namespace std;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	string a, b;
	cin >> a >> b;
	
	int min_diff = INT_MAX;
	for (int i = 0; i < b.size() - a.size() + 1; ++i) {
		int cnt = 0;

		for (int j = 0; j < a.size(); ++j)
			if (a[j] != b[j + i])
				++cnt;

		min_diff = min(min_diff, cnt);
	}

	cout << min_diff << '\n';
	
	return 0;
}